なたでぽぽ

数独の最小ヒント数問題解決

数独というパズルがあります。数年前にかなり流行したので、普通の人は知っていると思いますが、9×9の盤面に数字を入れていくあのパズルです。

私は結構このパズルが好きでして、数独まにあというサイトを運営していたり、ニコリという雑誌に自作の問題を載せてもらったりしています。

普通の数独問題では、最初から盤面に入っている数字(ヒントとか表出数字とか言います)の数は20個から28個くらいです。理由は、そのくらいのヒント数の問題が一番作りやすいからで、私が作る場合にも、特に意識しないと24個前後になります。

ただ、いつもヒント数24で作っていると、何だか同じような問題しか出来ませんので、見た目のスッキリした問題を作るために、頑張ってヒントの数を減らすという作業をよく行います。私の場合、ヒント数20が一番きれいに見えるらしく、この辺を狙っていることが多いです。

ヒント数20の問題は、それなりに作るのが難しいですが、少し頑張れば出来るというレベルです。ところがヒント数を18にしようとすると、問題を成立させるのが格段に難しくなります。これまで数独を何百問も作って来ましたが、ヒント数18の問題は数問しか作ったことがありません。

で、こうなると、ヒント数をどこまで減らせるのか、という事が気になります。

これまでにヒント数17の問題というのは知られていました。私も以前コンピュータを使ってヒント数が17の問題を何問か発見した事があります。そして、ヒント数が16の問題というのは今まで発見されていない、という状況でした。つまり、ヒント数の最小値は16か17のどちらかだろう、という状態だったわけです。

私としてはこの問題に非常に興味があり、チャンスがあれば挑戦してみたいと思っていました。感覚的にですが、ヒント数16の問題はない、という風に思っていましたので、それを証明するためにはヒント数16のパターンを全通り調べて、問題として成立する組み合わせが無い事を確かめればOKです。

理屈は簡単なのですが、その組み合わせが無茶苦茶多いというのが問題です。詳しい計算は省きますが、3GHzくらいのCPUで普通にやると、数十万年くらいは時間が必要な感じでした。これは間違いなく無理なので、何か革新的な方法を思いつかなければいけないという状況です。

私としても、ひまな時に何度か考えてはいたのですが、当然いい方法は思いつきませんでした。多分、この問題が解決されるのは、10年か20年くらい先なんだろうなあと、漠然と思っていました。

ところが、です。

何気にネットを彷徨っていると、この問題が解決されたというニュースが飛び込んできました。Natureによると、アイルランドの数学者Gary McGuireがヒント数16個のパターンを全部調べたとの事です。詳細についてはGary McGuireのサイトで公開されている論文に書かれています。

発見の内容にももちろん驚きましたが、この件がNatureの記事になっている事もビックリです。5年くらい前は海外でも「Sudoku」として大ブームだったものの、最近ではもう忘れ去られていると思っていましたので、こんなに注目度が高いのは意外です。まあ、数独好きの私としては嬉しいことではあります。

まだ詳しく論文を読んでいないので、証明の詳細については分かりませんが、コンピュータをフルに使った力任せのやり方のようです。おそらく理論的な面でもかなりの工夫があるのでしょうが、注ぎ込んたコンピュータパワーも相当なものです。

ルービックキューブは20手で解けるとか、 四色問題の証明とかもそうですが、最近はこういった方法がトレンドになっています。GPGPUやクラウド、グリッドもどんどん進化していますので、今後こういう話はますます増えるのでしょう。

数独ルービックキューブでの発見がどのくらい世の中の役に立つのかは分かりませんが、私の知的好奇心を満たすという意味では非常に重要です。世の中のマニアックな人たちは、今後も頑張って面白い成果を出してもらえればと思います。