数独の初期ヒント最小個数は「17」、それ未満では解けないと数学者が結論

by Miss_Bathory

日本だけではなく海外でも人気の高い数字パズル「数独(Sudoku)」。初期に配置するヒントの数は20個～30個ぐらいのものが多く、最小では17個のものが確認されていますが、問題として成立するのがいったいどのラインなのかは結論が出ていなかったのですが、アイルランドの数学者が「ヒントが16以下だと解けない」と結論を出しました。

Mathematician claims breakthrough in Sudoku puzzle : Nature News & Comment

Gary McGuire's Minimum Sudoku Page, Sudoku Checker

ユニバーシティ・カレッジ・ダブリンの数学者Gary McGuireさんは、数独においてヒントが16個以下のものは解法を持ちえないということを証明しました。このMcCuireさんの証明は、数学者たちの中で話し合いが持たれた結果、おそらく正しいであろうという結論が出されています。

「数独」とは「数字は独身に限る」の略。この名前はパズル制作会社ニコリが作ったもので、ニコリの登録商標になっており、日本のみならず海外でも「Sudoku」で通じます。また、ナンバープレイス(ナンプレ)とも呼ばれています。

by Wil C. Fry

数独は、最もポピュラーなものだと、9x9に区切られた格子の中に「タテとヨコで同じ数字が複数登場してはならない」「3x3の小格子の中で同じ数字が登場してはならない」というルールに従って、1～9までの数字を入れていくというもの。最初からいくつかの数字がヒントとして初期配置されており、オーソドックスなものではだいたい25個ぐらいの数字が記入されており、おおむね難度が上がると初期配置の数字の数が減ります。

by Jafin89

これまでに登場したパズルの中で、ヒントが最小だったのは17個で、16個以下のものは作れないのではないかと言われていました。これを証明するには16個のヒントが与えられた数独を解くという方法がありますが、コンピューターで計算しても相当な時間が掛かります。そのため、McGuireさんは問題を「hitting-set algorithm」を用いて単純化。2年間で700万CPU時間をかけて挑戦し、答えにたどり着きました。

McGuireさんは、今回の解法が数独だけではなく、遺伝子配列解明技術の分析や、セルラーネットワーク、その他の研究者による分析などに有用に用いられるのではないかと期待しています。

ちなみに、McGuireさん自身は数独よりもクロスワードパズルの方が好きなのだそうです。