最少ヒント数の数独

数独の問題として 成り立つためには、最低何個の表出数字があればいいのか？

これがいわゆるN=１７問題です。

世の中に出回っている数独の問題は、大体ヒント数が２０個から２８個くらいです。

このくらいのヒント数の問題が一番作りやすく、見栄えもいいというのがその理由でしょう。２０個よりもヒント数が少ない問題というのは作るのが急に大変になります。

それでも、ヒント数１９個、１８個の問題であれば何とか作ることが出来ます。

ただ、１７個となると本当に難しいです。

一般的に数独の問題は、見栄えを良くするために対称性を持っているものですが、今のところ対称性を持ったヒント数１７個の問題というのは知られていません。

ただ、対称性を気にしなければ、ヒント数１７個の問題というのは作ることが出来ます。

では、１６個ではどうか？

当然このような疑問が持ち上がりますが、この問題は今のところ未解決です。

予想としては、N=１６の問題はないと思うのですが、これを証明するというのは相当大変なことです。

ひとつの方法は、考えられるすべてのN=１６問題を試してみることです。ただ、数独の解盤面の数に書いたように、その組合せは天文学的になってしまいますので、現状のコンピュータの能力では現実的ではありません。

何か大きなブレイクスルーが必要なのは確かなのですが、誰もそれを見つけることが出来ないという状況が続いています。

いつ、誰が、どのような形でこの問題を解決するのか、とても楽しみです。

なお、Minimum Sudokuというサイトでは、ヒント数が１７である問題を収集しています。2009年4月現在、48,010個の問題が集まっており、その全てをダウンロードすることが可能です。

もし、N=１６の問題があるのであれば、このN=１７の問題の中に大きなヒントが隠されているはずなので、興味のある方は是非チャレンジしてみて下さい。

追記： 2012年1月1日、アイルランドの数学者Gary McGuireによって、N=16の問題は存在しないと証明されました！！！