|
数独は鉛筆と消しゴムを使って自分で解くのも面白いのですが、数学的にも非常にチャレンジングな興味深い問題を含んでいます。
例えば数え上げの問題。数独の答えとして現れる可能性のある盤面は何通りあるのか?知らなければ知らないで、どうということはないのですが、やっぱりこういうのは気になるものです。答えは
6,670,903,752,021,072,936,960 通り Sudoku
enumeration problems
世の中には偉い人がいるものです。また、回転や入替などの重複を除いて数えると、
5,472,730,538 通りになるそうです。 Sudoku
enumeration- the symmetry group
では、数独の問題として
成り立つためには、最低何個の表出数字があればいいのか?これがいわゆるN=17問題です。つまり、現状ではが表出数字が17個の数独問題は見付かっているのですが、16個の問題は見付かっていません。
果たしてN=17が最も数字が少ない数独問題なのか、それともN=16の問題が存在するのか?
これは非常に興味深い問題です。
N=17が最低であることを証明するためには、N=16の問題がないことを示さなければなりません。しかしながら上述のように組合せは天文学的な数字です。いくら最速のコンピュータを駆使しようとも、おいそれと計算できるような計算量ではないのです。いつ、誰が、どうやってこの問題を解決するのか?とても楽しみです。
私の感覚では、この問題を解決するためには、まだ十年近くの時間が必要だと思います。
そして結論はおそらく、N=17が最低である、ということになるのだと思います。 |