【ヴォイニッチの科学書】　Chapter-388　数独の重要問題が解けた

【iPad アプリ発売開始】

火技炸裂その美と花火の科学（通称：花火の科学）

花火の科学サポートページ　
 iTunes App Store 直リンク　

【次回のトークライブ】

DREAM SHIP Science Talk Live
教科書が教えないホットな科学の講演会２８
「次世代発電」
　　2012年6月2日（土）10時30分～11時30分
　　DREAM SHIP 下関市生涯学習プラザ　1階音楽練習室（山口県下関市）
　　入場無料・事前申し込み不要
　　会場地図　　

ダイナー・ヴォイニッチ　2012年東京夏
　　2012年7月下旬土曜日夜で23区内会場調整中

サイエンスアゴラ２０１１（未決定）
　　2012年11月10日（土）
　　東京・お台場

【ヴォイニッチの科学書《有料版》番組要旨】
2012年4月14日

Chapter-388　数独の重要問題が解けた　　

（前回の放送｜トップページ｜次回の放送）

　アイルランドの数学者が、複雑なアルゴリズムとスーパーコンビューターを用いて数百万時間に及ぶ演算を行い、解を1つしか持たない数独問題の作成には、少なくとも17個のヒントが必要であることを示しました。16個以下のヒントでは解が1つに定まらず、有効な問題にならないようです。
この発表に対して、世界の数学者たちはおおむね内容に納得するコメントを出していますし、数独を数学的研究対象にするという新興分野に重要な進展をもたらしたという意見も多かったと言うことです。このことは、数独愛好家たちが以前から、ヒントが17個の数独はあるが、16個の有効な数独は見当たらないことに気付いており、16個のヒントで解が1つに決まるようなものは存在しないのではないかという推測が広がっていたことと一致します。

　これを証明する方法の1つは、答えが成立するすべての解答に対し、その盤面を解とするヒントが16個の有効な数独問題があるかどうかを総当たり的に検証することですが、演算に時間がかかりすぎます。そこで今回の研究者らは、「ヒッティング・セット・アルゴリズム」という仕組みを設計して、この問題を単純化しました。その方法とは数学的に「不可避集合」と呼ばれる仕組みです。研究者らはらは、2年かけてこのアルゴリズムのテストを行い、その後、アイルランド・ハイエンド・コンビューティング・センター(ダブリン)のコンピューターで700万CPU時間をかけて解析し、今回の結果を得ました。

◇　　◇　　◇

（FeBe! 配信の「ヴォイニッチの科学書」有料版で音声配信並びに、より詳しい配付資料を提供しています。なお、配信開始から一ヶ月を経過しますとバックナンバー扱いとなりますのでご注意下さい。）

ヴォイニッチの科学書は株式会社オトバンクが発行するオーディオブック番組です。
定期購読はこちらからお申し込みいただけます。
このサイトでは番組のあらすじを紹介しています。無料で閲覧できます。