数独まにあ ルービックキューブ  エクセルまにあ  あらのHP  麻雀研究所  株式投資  なたでぽぽ


最少ヒント数の数独

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

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

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

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

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

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

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

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

では、16個ではどうか?

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

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

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

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

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

 

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

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

 

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