数独の数学：なぜヒントは最低17個必要なのか——66垓通りの盤面と7億時間の計算機証明

ナンプレを解いていて、ふと考えたことはないでしょうか。「ヒントの数字は、最低いくつあれば答えがひとつに決まるのだろう？」

答えは 17個 です。ヒントが16個以下の数独には、解がひとつに定まる問題（唯一解の問題）が存在しません。ただしこの事実、誰かが鮮やかな数式で示したものではありません。証明が完成したのは2012年、使われた道具は紙とペンではなく、約700万時間分のCPU計算でした。この記事では、その証明に至る数独の数学を順に見ていきます。

まず、数独の盤面は何通りあるのか

出発点は「完成した9×9の盤面（すべてのマスが埋まった正しい盤面）は何通りあるか」という問題です。2005年、バートラム・フェルゲンハウアーとフレイザー・ジャービスがこれを計算し、答えは

6,670,903,752,021,072,936,960 通り

と判明しました。約 6.67×10²¹、日本語の数の単位でいえば約66垓（がい）通り。仮に1秒に1枚ずつ完成盤面を作り続けても、宇宙の年齢の1万倍以上かかる数です。

ただし、この中には「実質的に同じ」盤面が大量に含まれています。盤面を90度回転しても、行を(ルールを保つ範囲で)入れ替えても、数字の1と9を全部交換しても、パズルとしての構造は変わりません。こうした対称操作で移り合う盤面を同一視すると、本質的に異なる盤面の数は2006年にエド・ラッセルとジャービスによって

5,472,730,538 通り（約54億7千万）

と計算されました。66垓が54億まで減る——対称性というレンズがいかに強力かが分かります。ちなみにこの計算には、群論の「バーンサイドの補題」という、まさに「対称なものを数える」ための定理が使われています。

17ヒント問題の歴史

完成盤面からヒントをどこまで間引けるか。この問いは2000年代前半から愛好家と研究者の競争テーマでした。オーストラリアの数学者ゴードン・ロイルは世界中から17ヒントの唯一解問題を収集し、そのコレクションは最終的に約49,000問に達しました。17個の実例は山ほどある。ところが、16個の実例はただの一問も見つからない。何年探しても、です。

図：実在する17ヒント問題の一例。数字はたった17個ですが、解はただひとつに定まります

「見つからない」と「存在しない」の間には、数学的には深い谷があります。この谷を埋めたのが、アイルランド・ダブリン大学のゲイリー・マクガイア、バスチアン・トゥーゲマン、ジル・チヴァリオの3人による2012年の研究「There is no 16-Clue Sudoku」でした。

証明のアイデア：「不可避集合」を撃ち落とす

54億の本質的に異なる完成盤面すべてについて、「16個のヒントで唯一解になる問題が作れないこと」を確かめる——これが証明の骨格です。しかし、1つの盤面から16マスを選ぶ組み合わせは約33兆通り。総当たりでは54億×33兆で、どんな計算機でも終わりません。

鍵になったのが**不可避集合（unavoidable set）**という概念です。たとえば、完成盤面の中に

 ある2行・2列の交点の4マス

   … 1 … 9 …
   … 9 … 1 …

のような配置があったとします。この4マスの 1 と 9 をそっくり入れ替えても、行・列・ブロックの制約はすべて保たれてしまう——つまり別の完成盤面ができてしまいます。ということは、この4マスにヒントが1個もなければ、解く人には2つの解を区別する手段がなく、唯一解になりえません。このような「最低1個はヒントを置かないと解が分岐してしまうマスの集合」が不可避集合です。

すると問題はこう言い換えられます。「その盤面のすべての不可避集合に最低1個ずつ触れるような16マスの選び方はあるか？」——これは計算機科学でヒッティングセット問題と呼ばれる有名な問題の形です。マクガイアらはこの構造に特化した高速アルゴリズムを開発し、各盤面について小さな不可避集合を数百個列挙しては、16マスでそれら全部に触れる方法がないことを確認していきました。

計算はダブリンのスーパーコンピュータで2011年の1月から12月までほぼ丸1年実行され、総計算量は約700万CPU時間。結果、54億盤面のどれからも16ヒントの唯一解問題は作れないことが確認されました。17という数字は、この瞬間に「経験則」から「定理」になったのです。

上限側の話：ヒントが77個あっても解けないことがある

下限の17と対になる、あまり知られていない事実も紹介しておきましょう。ヒントは多ければ多いほど安全、とは限りません。先ほどの不可避集合を思い出してください。1と9が長方形に並んだ4マスの不可避集合を持つ完成盤面から、ちょうどその4マスだけを空欄にした問題を作るとどうなるか。ヒントは 81−4＝77個もあるのに、1と9の入れ方が2通り残り、唯一解になりません。つまり「唯一解を保証できないヒント数の最大値」は77です。ヒントの多さではなく、どの情報が欠けているかがすべてを決める——不可避集合の考え方が、下限の証明にも上限の反例にも同じ顔で現れるのが、この理論の美しいところです。

もうひとつ、極小パズル（minimal puzzle）という概念があります。どのヒントを1個削っても唯一解が崩れる、無駄のない問題のことです。17ヒント問題はすべて自動的に極小ですが、逆に極小でありながらヒントが多い問題も存在し、これまでに見つかっている最大の極小パズルは40ヒント。40個も数字が並んでいるのに、どの1個を消しても解が分岐する——直観に反する、なかなか不気味な物体です。

「計算機証明」は証明と呼べるのか

四色定理のときから続く古典的な論争ですが、注目すべきは検証可能性です。マクガイアらのアルゴリズムとコードは公開されており、2013年には別グループが独立の再計算で結果を追認しています。数学界では現在、この結果は確定した定理として扱われています。

面白いのは、「なぜ17なのか」を人間が直観できる短い説明は、いまだに存在しないことです。66垓という総数も、54億という対称類の数も、17という下限も、すべて「計算したらそうだった」としか言えない。数独という単純なルールの奥に、要約を拒む複雑さが横たわっている——ここがこの分野の一番の醍醐味だと私は思います。

遊ぶ側にとっての意味

実用面での補足をひとつ。「ヒントが少ないほど難しい」と思われがちですが、これは誤解です。17ヒント問題には隠れたシングルだけで解ける易しいものが多くあり、逆に25ヒントでも Swordfish 級の手筋を要求する難問は作れます。難しさを決めるのはヒントの数ではなく、解く過程で要求される論理の深さです。当サイトの毎日の20問も、ヒント数ではなく必要テクニックで初級から鬼級までを分けています。

もし手元の問題が唯一解かどうか気になったら、ナンプレソルバーに入力してみてください。また、解くための具体的な手筋はテクニック集に、腕試し用の過去問はアーカイブにまとめてあります。

今日あなたが解く1問は、66垓の盤面の中からたった1つを選び、54億の対称類のどこかに属し、17個以上のヒントという数学的な下限の上に成り立っています。9×9の小さな枠の向こうに、それだけの数学が広がっていることを、ときどき思い出してみてください。