「世界で一番難しい数独」の難しい問題
2013年3月13日 18:38
あるAnonymous Coward 曰く、 東京大学の渡辺宙志助教が、スパコンを用いて「世界で一番難しい数独」を作る試みを行っている。この結果、氏が「2013年3月現在、おそらく世界で一番難しい問題」を発表したのだが、実はこれは人間が簡単に解くことができる問題だった模様。
「難易度の定義」は難しいが、数独の解法とされている「Pencil Marks法」や「Recursive Backtracking法」を使い、探索に必要となる深さを難易度の尺度にしたという。が、判定アルゴリズムにミスがあり、難しくない問題を「難しい」と誤判定していた模様。これを修正した「難しい数独」が再度公開されている。
スラッシュドットのコメントを読む | サイエンスセクション | サイエンス | 数学
関連ストーリー：
正規表現クロスワード、解ける？ 2013年02月16日
「世界一難しい数独」 2012年07月06日
数独、少なくとも17カ所埋められていないと問題として成立しない 2012年01月10日
数独を解く大腸菌 2010年11月20日