ヒント16個のナンプレの証明をちょいと覗いてみた

　ナンプレはみなさんご存じのパズルですね。
　ところで、「ヒント数字が16個であるナンプレ問題は存在しない」という事実はご存じでしょうか？
　当ページでは、その証明に使われたアイデアにちょいと迫っていきます。
　……が、めちゃくちゃ長くなった😅
　ヒマでしかたがない時にでもご覧ください。

１．ナンプレ界をにぎわしていた、大きな問題があった

　昔から、ナンプレには問題が１つありました。

　雑誌など巷に出回っているナンプレには、通常、24個前後のヒント数字が書かれています。
　そこからスタートして残り57個程度の空白マスを数字で埋めていき、ナンプレを完成させていくわけですね。
　当然ですが、ヒントの個数に規定はありません。
　唯一解を持つ物ならヒントは何個あっても良く、難易度などに応じて多かったり少なかったりします。
　たまに20個くらいしかないナンプレもあったりする。

　ヒントの少ないナンプレを作るのは非常に難しい。
　だから、それにチャレンジしたくなる人も現れる。
　そして、「ヒント個数のギリギリを知りたい」という欲求も自然な流れと言えるでしょう。

ナンプレ問題図にあるヒント数字、どこまで少なくできるんだろう？

　これが昔からの問題だったんです。

　この問題、多くの数学者達も注目するほどの大きな物でした。
　2000年代中頃にはこの最少ヒント数問題について雑誌などで言及があり、その後コンピュータを使った研究がなされました。
　2008年頃、オーストラリアの大学で「ヒント８個のナンプレに唯一解は存在しない」ことを確認し、その翌年には「ヒント12個でも唯一解には不十分」を示すためのコンピュータ計算をほとんど完了していたようです。
　2010年には、台湾の大学で「ヒント16個のナンプレが存在するかどうか」の探索が開始されました。同年の『人工知能の諸技術に関する国際会議（TAAI）』のプロシーディング（論文冊子）にも 最少ヒント数問題 が収録されています。この探索チームは、2011年末の時点で14億個以上ものナンプレを検証し終えていました。

　他にもこんな話があったりします。
　2008年には、なんと17歳の女性が「ヒント16個のナンプレは存在しない」ことを証明したという！
　『Jugend forscht（ドイツの青少年科学コンテスト）』にエントリーし、Junge Wissenschaft 誌にも発表したそうです。
　ただ、その証明には穴があったようで、せっかくの証明は残念な結果に終わってしまいました。
　もし証明が正しければ、あるいは穴を直すことができれば、「17歳少女が証明した！」という事実は数学界やナンプレ界にかなり衝撃を走らせたかもしれませんね。

図 1-1

　ちょいと１枚のナンプレ完成図を紹介しましょう。
　図1-1 です。
　まぁ、見た目は何の変哲もない完成図ですね😅

　しかし、この完成図はそんじょそこらの完成図とは違います。
　実は、この盤面からはヒント17個の問題図を29個も作れるんです。
　81個の数字からうまいこと17個をヒント数字にして問題図を作る。すると、それはちゃんと唯一解を持つという！

　ヒント17個って、実はすごいことなんです。
　ヒント24個未満のナンプレを作ること自体が大変なのに、ヒント17個は至難の業。もはや神の領域。
　１つの盤面に神29柱も宿っているとは、神秘的としか言いようがない。

　この「29個」という記録、2010年前後の時点では未だ破られていません（現在はどうかはわかりません）。
　こんなにも凄い盤面なら、これを徹底サーチすれば16ヒントナンプレが見つかりそうな気がしますよね！
　そういう期待が高まるのは当然であり、実際、肯定的解決の有力候補でした。

　しかし、別の視点に立つと、否定的な解決も見えてくる。
　もし仮に16ヒントナンプレが存在したとすると、65個（81－16＝65）ある空白マスの１つにヒント数字を入れてしまえば「１つの盤面に17ヒントナンプレが65個もできる」わけですよね。
　なのに、最高記録がたったの29個とはどういうことか？
　そのギャップの説明がつかず、「唯一解を持つ16ヒントナンプレはどうやら存在しそうにない」とも予想できるんです。
　果たしてどちらに軍配が上がるのか。
　当時はまだ「神のみぞ知る」でした。

　いろんな議論が飛び交った難問でしたが、2012年１月、とうとう解決の時が訪れます。
　否定的な解決ではあったけれど、それでも「ヒント数字の最少は17個」は大きな結論だと言えるでしょう。

　その証明方法はと言うと、「プログラムを組んでゴリゴリ実行した」で終わりです😅
　でも、そこには秀逸なアイデアや数学的な理論が取り入れられて工夫がなされていた。
　その部分を話していこうかと思います。

　ここで、ひとつ注意書き。
　当ページの内容は、Gary McGuire, Bastian Tugemann, Gilles Civario の３人による論文『There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration』（2013年９月改訂版）を基にしています。
　当ページでは、この論文を「原論文」と呼ぶことにします。
　原論文の内容を正しく解釈して話すことを心掛けていますが、誤訳や誤解釈をしている可能性はゼロとは言えません。
　また、なるべく話をわかりやすくするために厳密性を欠いている箇所もあります。
　したがって、当ページの正確性について完全な保証はできません。
　正確な内容を知りたい方々は、当ページではなく原論文をご覧ください。
　原論文は学術記事サイト『arXiv』のこのページでダウンロード可能です。

２．単純にやると酷い目に遭う

　証明すべき結論は「唯一解を持つ16ヒントナンプレは存在しない」です。
　ということは、「ヒント16個」に注目した具体的方法を考えるのが普通と言えますね。
　とりあえず、最も直線的な方法はこれかな？

完成図から単純に数字を16個選んでヒント数字にする。
果たして、そのナンプレは解けるだろうか……？

　ナンプレの完成図に並んでいる81個の数字のうち16個を残し、他の数字を全部消去する。
　そうしてできたナンプレが解けるかどうかを確かめる。
　この方法をシラミ潰しで行う。
　もぅ単純明快！　誰もが思いつくやり方ですよね。

　ところが、この方法はいとも簡単に頓挫するんです。
　それはなぜか？
　まずは１つ計算してみましょう。
　81個の数字から16個を選ぶ。それは何通りあるだろうか？

\[ {}_{81}\mathrm{C}_{16} = \dfrac{81\cdot80\cdot79\cdots66}{16\cdot15\cdot14\cdots1} = 33,594,090,947,249,085\,\text{通り} \]

　１個のナンプレを検証するのに、３京3000兆通り以上もの数字選択が必要です😅
　もぅもぅもぅ、この回数だけでノックアウトです😅

　しかも、これは「たった１個のナンプレ完成図に対する回数」です。
　当然、完成図がたった１個だなんてわけがない！
　では、全部で何個あるのだろう？
　その個数は…… 6,670,903,752,021,072,936,960個 です。

　なんだか聞いてて一瞬脳ミソが止まるような数ですよね。
　わかりやすく４桁に区切ってみますよ。

66,7090,3752,0210,7293,6960個。

　66垓です😅
　ガイですよ、ガイ😅
　９×９サイズのナンプレの完成図は、全部で66垓個もあるんです。

　まぁ、一応「垓」という命数は世の中に無いわけじゃぁありません。
　例えば、サイト『物質・材料研究機構（NIMS）』によると、一円玉を構成するアルミニウム原子は 約222垓個 あるそうです。
　他には、サイト『お札と切手の博物館』によると 10垓ペンゴ なんていう紙幣が発行寸前だったとか。
　でも、やっぱり桁外れに多いよね😅

　3.3京に66垓。
　単純な方法だと途方もないどころの話じゃぁないんですね。
　3.3京×66垓のループ処理なんて、コンピュータですらサジを投げます😅
　この「個数」という壁が天を貫くほど高すぎる。

　ただ、これに関しては朗報があります。
　実は、この66垓個は、ほんの少し異なっていても別物として数えています。
　例えば、数字１と２を交換しただけ、ヨコ２列を交換しただけ、盤面を裏返しにしただけ、etc...
　当サイトの『ナンプレ完成形はどこまで増やせる？』というページでは、１つの完成図に数字置換やら列交換やら変換をアレコレ施して別の完成図をたくさん作りました。
　そのページでは「４兆個できた」「１兆個だ」などとしゃべっていますが、それらの完成図は全て本質的に同じです。
　例えば、個々の数字はただの記号に過ぎないから、数字１〜９を入れ替えたところで本質は変わらないですもんね。
　だから、それらを１個ずつ検証しても意味はありません。論理展開も結論もダブりまくって無駄なだけ。

　というわけで、「本質的に異なる完成図だけを相手にすればＯＫ！」となるんですね。
　その個数は既に判明しています。
　全部で 5,472,730,538個 です。
　よって、66垓個ではなく54億個だけを対象にすれば良いわけです。

　……とは言っても、3.3京×54億でもコンピュータはサジを投げます😅
　だから、単純な方法では問題解決など夢のまた夢なんですね。
　というわけで、別のところに注目する必要がある。
　次セクションでは、唯一解の本質部分に目を向けてみましょう。

３．複数解のカギを握る set がある

　証明すべき結論は「唯一解を持つ16ヒントナンプレは存在しない」です。
　だから、唯一解という物について考察しなければいけません。
　さて、この「解を１つだけ持つ」を具体的にどう捉えればいいんでしょう？

　そのために、あえて逆の発想をしてみましょう。
　つまり「ナンプレが複数解を持つとはどういうこと？」と考える。
　そして、さらに一歩進んで、こういうことを考えるんです。

ナンプレに複数解をもたらす元凶って、一体何だ？

　この「元凶」の正体がわかれば、あとはそれらを全部潰してしまえばいい。
　そうすれば、自ずと唯一解に至る。
　こういう発想です。

図 3-1

　図3-1 の黄色４マスに注目しましょう。
　実は、この４マスには特徴が１つあります。

  • 数字２と７を入れ替えると別の完成図ができてしまう。

　この「別の完成図が」というのが重要で、これが複数解の原因になるんです。
　この黄色４マスを unavoidable set と呼びます。
　この unavoidable set というヤツが複数解をもたらす元凶です。

　ちなみに、図3-1 の青色６マスも unavoidable set です。
　数字を入れ替えても別の完成図ができあがるので、ヒマでヒマでしょーがない時にでも確認してみてください😊

　さて、なぜ unavoidable set が元凶になるんでしょう？
　それは下図を見ればわかります。
　図3-1 から適度に数字を残して問題図にする。その際、黄色 unavoidable set には数字を一切残さない。
　そうしてから、このナンプレを解いてみましょう。
　すると……残念なことになっちゃうんです。

　どんなにうまく解き進めたとしても、黄色４マスが絶対に埋まらない。
　しかも、黄色マスの１つに数字２を入れても７を入れても、ナンプレが完成できてしまう。
　つまり、この問題図は複数解を持っているんです。
　さらに言うと、黄色以外の77マス全部にヒント数字があったとしても唯一解にはなりません。

そうかぁ。
黄色マスのどこかにヒント数字が絶対必要なのか……。

　実は、ナンプレが唯一解を持つためには、絶対に満たさなければならない重要な条件があります。

　unavoidable set はヒント数字を必ず持たなきゃいけない。
　逆に言えば、ヒント数字のない unavoidable set は存在してはならない。
　こういうことなんですね。
　ちなみに、上図の青色 unavoidable set では数字が一意に決まりましたが、それはヒント数字を持っていたからです。

　このように、unavoidable set は複数解の発生に関して大きなカギを握る存在です。
　本質部分だと言っても過言ではない。
　そこに目を向けると、問題解決へ向けて戦略が１つ見えてきそうですね。

ナンプレ完成図の中にある unavoidable set を全て見つける。
そして、その unavoidable set 達のどれもがヒント数字を持つように、数字を16個選ぼう！

　セクション２では、本質的に異なるナンプレ完成図は54億個だと述べました。
　その54億個を対象に、１個ずつこの作業をやっていく。
　こういう戦略です。

　手順をおさらいしましょう。

  1. 完成図の中に存在する unavoidable set を全て見つける。
  2. 「完成図から数字16個をうまく選んでどの unavoidable set もヒント数字を持つようにできるか？」を検証する。
  3. 1.〜2. の作業を 5,472,730,538個の完成図に対して行う。

　もちろん手作業では無理です。でも、理論上は可能になった。
　だから、後はコンピュータを使って証明すれば良い！
　問題解決へのシナリオができました。

　そういや、unavoidable だなんて一風変わった名前ですよね。
　これって……「ヒント数字が入ることを避けられない」という意味かもしれないね😊

４．minimal という名の大事な set

　「理論上は可能」とは言ったけど、世の中、シナリオ通りにいかないことは往々にしてありましてね。
　残念ながら、前セクションの手順そのままではうまくいかないんです。
　unavoidable set というヤツは思いのほか複雑で、それらを見つける作業が非常に困難なんです。
　（どれだけ複雑かは別ページで説明しています）

　というわけで、前セクションの手順 1.〜3. は捨てちゃいます。
　実際は、原論文のチームは次の手順をたどりました。

  1. 完成図の中にある（12マス以下の）minimal unavoidable set を全て見つける。
  2. その set 達を基に、唯一解を持つ可能性のある問題図を全て作成する。
  3. それらが本当に唯一解を持つかどうかを１個ずつ検証する。
  4. 1.〜3. の作業を 5,472,730,538個の完成図に対して行う。

　unavoidable set ではなく、minimal unavoidable set に目を向けたんです。
　実は、問題解決にあたって unavoidable set を全部見つける必要はありません。一部だけで事足ります。
　その理由はセクション4-2で説明しましょう。

　さて、「minimal」なんて新しいワードが出てきましたね。
　minimal とは一体何だろうか？
　それを説明しましょう。
　ただし、原論文による定義は複雑なので、当ページでは簡略化して説明します。
　（minimal の詳細は別ページで説明しています）

4-1．minimal unavoidable set とは何ぞや？

図 4-1

　図4-1 の黄色６マスを見てみましょう。
　この６マスは unavoidable set ですが、特殊な性質を持っています。

  • どの黄色１マスにヒント数字を置いても、他の全ての黄色マスに自動的に数字が確定する。

　言い換えると、「黄色のどこでもいいからヒント数字を１個置けば、黄色６マスに複数解は生じない」ということです。
　「minimal である」とはこういう unavoidable set のことを指します。

　対して、青色８マスは違います。
　右下隅の４と７をヒント数字にしても、残り６マスは未だに unavoidable set であり自動的に数字は決まりません。

　黄色６マスは minimal です。
　青色８マスは minimal ではありません。

　「minimai」の定義をしておきましょう。

  • Ａを unavoidable set とする。
    Ａのどの１マスにヒント数字を置いてもＡに複数解が生じなくなる時、Ａを minimal unavoidable set という。

　ちなみに、minimal は「最小限の」という意味です。
　図4-1 の黄色領域は現在６マスですが、これ以上マスが減るとヒント数字なしでも数字が全て確定します。
　「unavoidable set であるためにはこのマス数が最小限」という意味で minimal というわけですね。

　minimal unavoidable set の例をいくつか挙げましょう。
　青色・赤色・緑色・紫色、全て minimal unavoidable set です。

4-2．実は minimal だけで良いのさ

　そういえば、なぜ手順 1. では minimal unavoidable set だけを探すんでしょう？
　その理由を説明しましょう。

　セクション３ではこう述べました。

  • 問題図が唯一解を持つためには、どの unavoidable set もヒント数字を持つ必要がある。

　問題図が唯一解を持つ時、どの unavoidable set にもヒント数字が入っています。
　いわば、「ヒント数字達が unavoidable set を完全網羅している」という状態です。
　ということは、その一部である minimal unavoidable set もヒント数字達は完全網羅しているわけですね。

　これは、逆に言うとこうなります。

  • ヒント数字達が mininal unavoidable set を１つでも見逃していたら、もうその問題図は唯一解を持たない。

　不備１つでもう「論外」となってしまう！
　当然、そういう問題図は検証しても意味がありません。

　実は、この事実を利用したうまい方法があります。
　まず最初に、そういう不備のある問題図を全て不合格にしてしまうんです。
　すると、残りは唯一解の可能性を秘めている問題図ばかりになる。それらを実際に検証していくんです。
　オーディションで言う「書類審査→最終審査」みたいなやり方ですね。
　これは作業効率アップに繋がる有用な方法です。

　というわけで、その「書類審査」の合格基準とするために minimal unavoidable set 達が必要となる。
　そこで、前もってそれらを全て収集しておくわけです。
　これが手順 1. で行う作業です。

　一般の unavoidable set を全て収集するのは困難ですが、minimal だと正確に収集する方法があります。
　しかもその個数は少ないので扱いやすいというメリットもあります。
　詳細はセクション4-3で説明しましょう。

4-3．どうやって minimal unavoidable set を集めるのか？

　というわけで、問題解決のために必要な unavoidable set は minimal だけで良いということになりました。
　じゃぁ、ここから先は minimal unavoidable set を MUS と略しちゃいましょう！
　長いですもんね。
　いちいちミニモゥアナヴォイダボゥセ〜ッなんて言ってたら、舌を噛むことが unavoidable（避けられない）😅

　さて、原論文のチームは、どういう方法で完成図から MUS 達を見つけていったんでしょう？
　実は「blueprint」と呼ばれる物が既にありました。
　blueprint とは MUS の本質的な形を記した標本です。
　ナンプレのオンラインフォーラムでは、Ed Russell という人物が unavoidable set を調査していて blueprint のリストを作り上げていたそうです。
　原論文のチームはそのリストを貰って活用していきました。
　一部を紹介しましょう。

　１つの完成図から MUS を探す時、リスト内の全ての blueprint に照らし合わせてパターンマッチングを行います。
　下図のように、各 blueprint と本質的に同じ MUS を続々と拾い上げるわけです。
　ただ、本質的に同じ blueprint は重複して記されてはいないから、下図の赤色や青色なども全て拾えるように実際はうまく工夫して探していきました。

　実際は、原論文のチームは「12マス以内の blueprint を用いる」という方法をとりました。
　一般の完成図に対して、MUS は360個ほど集まったそうです。
　当然ですが、それらの MUS は全て12個以下のマスで構成されています。

　原論文でも感想が書かれていますが、完成図によって MUS の個数に相当なバラつきがあったみたいですね。
　かたや500個程度、かたや200個未満。
　興味深いことに、前者の場合「小サイズ（４マスまたは６マス）の MUS は比較的少ない」ということが多いのだそう。
　へぇ〜、小サイズだらけで500個とかありそうに見えるのにね。

５．さぁ果たして16ヒントナンプレは存在するか？

　さて、手順 1. を終えて、完成図から12マス以下の MUS が全て集まりました。
　次は手順 2. を行いましょう。
　この MUS 達を基に、唯一解を持つ可能性のある問題図を作成します。

　そういや、セクション4-2では、こう述べましたっけ。

ヒント数字達は全ての MUS を完全網羅していなきゃいけない。
MUS を１つでも見逃していたら、もうその問題図は唯一解を持たない。

　「不備１つでもう論外となる！」と叫んだヤツです。
　実は、このことは MUS を12マス以下に限定したとしても成り立ちます。
　そこで、ここからは「MUS は全て12マス以下である」として話を進めていくことにします。

　不備１つで不合格となってしまう。
　ということは、手順 2. を行う時は不備を起こさぬよう、収集した MUS の中から16マスを選ぶことにします。
　その16マスの数字で問題図を作り、それが唯一解を持つかどうかを検証するわけです。
　マス選びの具体的な手順はこんな感じ。

  1. ある MUS から１個目のマスＡを選び、Ａを含む全ての MUS に印を付ける。
  2. まだ印の付いていない MUS から２個目のマスＢを選び、Ｂを含む全ての MUS に印を付ける。
  3. まだ印の付いていない MUS から３個目のマスＣを選び、Ｃを含む全ての MUS に印を付ける。
  4. 以下、４個目、５個目、……と繰り返す。

　全ての MUS が書かれたチェックシートを作っておく、と捉えるとわかりやすいですね。
　マスを１個選ぶたびに、該当の MUS にチェック印✔️を付ける。
　16マスに到達するまでに全ての MUS に✔️が付けば合格！　その問題図は唯一解の可能性を秘めています。

　なお、マス選びをする際、既に✔️の付いた MUS から選ぶ必要はありません。
　なぜかと言うと、セクション4-1で説明した minimal unavoidable set の性質により、次の２つが許されるからです。

　✔️が付いた時点でその MUS 内部にヒント数字が置かれることが確定し、その MUS 内部では複数解が起こりません。
　よって、同じ MUS からわざわざ２個も３個もマスを選ぶ意味はないんです。

5-1．本当にこの方法で大丈夫？

　ただ、ここでちょいと疑問が１つ出てきます。
　セクション4-3の末尾で軽く述べましたが、MUS は全て12マス以下なんです。
　13マス以上は１つもない。それどころか、unavoidable set 全体から見てもほんの一部でしかありません。

そんな少ない MUS 達だけで、唯一解の可能性のある問題図を全部作れるんだろうか……？？

　いかにも検証漏れが起きそうで怖いですよね。
　しかし、その心配は要りません。
　その理由を説明しましょう。

　チェックシート法で MUS の中からマスを選んでいった時、選択マスの組み合わせは数多く存在します。
　そして、マス選びの結果は３通りに分かれます。

【１】
16マスを選んでも全ての MUS を完全網羅できなかった。
【２】
16マスを選んで初めて全ての MUS を完全網羅した。
【３】
16マスに達する前に全ての MUS を完全網羅できた。

　【１】の場合は不合格です。
　完全網羅が絶対必要ですもんね。

　【２】の場合は合格。唯一解の可能性を秘めています。
　その16マスの数字で問題図を作って検証すればＯＫです。

　【３】の場合も合格。唯一解の可能性を秘めています。
　ただし、さらにマスを何個か追加して16マスに増やしてから問題図を作ります。
　以下で詳しく説明しましょう。

図 5-1

　２つの数字ａ, ｂのある全18マスは unavoidable set だから、どのマスも必ず何かしらの unavoidable set に属しています。
　だから、unavoidable set 達は必ず盤面全体を覆い尽くします。
　しかし、12マス以下の MUS では盤面を覆いきれない可能性が出てきます。

　図5-1（※イメージ図です）を例にとりましょう。
　色の付いた領域が MUS だとします。
　どの MUS にも覆われていないマス（白色）がありますね。
　そして、13マス選んだ時点で MUS 達を完全網羅できました。

　この時、その13マスを含む問題図をたくさん作れます。
　具体的には、未選択の68マスから３マスを選んで合計16マスに増やしてから問題図を作るんです。
　そして、それらを全て検証します。
　これは 68Ｃ3 通りのローラー作戦をすれば良いだけなので、未選択マスがそれぞれどの unavoidable set に属するかを知らなくてもＯＫです。

　この【２】【３】で得られた問題図、これが検証すべき物の全てです。

　あ、「チェックシート以外の方法だと他の問題図ができるんじゃない？」という疑問も出てきそうだ。
　でも、これも心配には及びません。
　チェックシート法を使わずに適当に16マスを選んだとしても、結果はやっぱり【１】【２】【３】のどれかになります。
　たまたま【２】【３】の場合に該当したとしても、その問題図は今述べた「検証すべき物の全て」の中に含まれています（【３】の場合はローラー作戦の問題図の１つに当てはまる）。
　したがって、12マス以下限定の MUS でも大丈夫なんです。

　原論文のチームが12マス以下に限定した理由は、作業効率化のためです。
　全ての minimal unavoidable set を収集対象にすると、16マス選ぶのに時間がかかる。かと言って、マス数の少ない set ばかりだと【３】のパターンが激増してローラー作戦だらけになる。
　このジレンマの折衷案が「12マス以下限定の MUS 収集」だったのでしょう。
　原論文では「12以下の要素を持つ unavoidable set 達が総合的にベストな結果を与えるということがわかった」と述べています。

5-2．あとは１個ずつ検証して結論へ

　さぁ、12マス以下の MUS でも手順 2. には差し支えないということがわかりました。
　安心して問題図を作っていけますね。

　チェックシート法の手順をもう一度。

  1. ある MUS から１個目のマスＡを選び、Ａを含む全ての MUS に印を付ける。
  2. まだ印の付いていない MUS から２個目のマスＢを選び、Ｂを含む全ての MUS に印を付ける。
  3. まだ印の付いていない MUS から３個目のマスＣを選び、Ｃを含む全ての MUS に印を付ける。
  4. 以下、４個目、５個目、……と繰り返す。

　この作業の進め方は簡単です。
　まず、６マスの MUS を最初に選んだとすると、マスＡの選び方は６通りある。
　最初の MUS からは６つに分岐する。
　分岐先のそれぞれに対してマスＢ選択用に MUS を選び、そこからさらに分岐する。
　さらにマスＣ選択用に MUS を選んで分岐する。
　これを繰り返します。
　最終的には「ツリー構造」と呼ばれる枝分かれ構造ができあがります。

　後は、それぞれの末端までツリーをたどってマスを拾い上げ、問題図を全部作って手順 2. は終わり。
　手順 3.「その問題図達が唯一解を持つかどうかそれぞれ検証する」に移ります。
　これが１個の完成図に対する作業の全てです。
　これを 5,472,730,538個の完成図に対して行い（手順 4.）、16ヒントナンプレが存在するか否かを調査すれば全行程終了です。
　結果は……

  • 「ヒント16個のナンプレ問題は１つも存在しない」でした。

　「ヒント16個のナンプレ問題は存在するか？」
　原論文のチームによるこのプロジェクトは、2005年８月に始まりました。
　ナンプレ完成図をくまなく探索するためのソフトウェア「checker」を開発し、ゴールへ向けての第一歩を踏み出しました。
　2007年中は休眠状態だったものの、2008年下半期には checker の高速化のヒントを得てプロジェクトを再開。
　2009年初めに２代目の checker をゼロから開発し、二度目の旅立ちをしています。

　その旅は約３年もの長い月日をかけ、2012年１月１日、大きなゴールへとたどり着いたのでした。

６．おまけ

　ここからは余談です。
　ちょっとした話を２つしましょう。

6-1．ちょっとした工夫を紹介

　手順 2. の「マス選び」に施した工夫をちょびっと紹介しましょう。
　まず、簡単な工夫は「収集した MUS 達をマス数の少ない順に並べ直した」ということ。
　先頭には４マスの MUS を並べ、続いて６マス、８マス、……最後は12マスの MUS、と昇順にソートしたわけです。
　これは序盤の分岐の量を抑えるためです。

　次に、「複数の MUS 達を１つにまとめて clique という物を作る」というアイデアも盛り込みました。

図 6-1

　まず「clique って何だ？」だと思うので、その説明から。

　図6-1 には２つの MUS がありますね。黄色と緑色です。
　そして、この２つは重なっていません。つまり、マスを共有していません。
　この時、黄色と緑色をまとめて「14マスの unavoidable set」とみなすことができますね。
　このように、重なりの全くない MUS を１つにまとめてできた unavoidable set を clique と呼びます。

　黄色＋緑色の clique にヒント数字が２個必要だということは明らかですね。
　これを 次数２の clique と呼びます。
　一般にはこう定義されます。

  • 互いに重ならないｎ個の MUS を合成させてできた unavoidable set を 次数ｎの clique と呼ぶ。

　次数は「必要なヒント数字の個数」そのものですね。

　この clique も手順 2. の効率化に大きく貢献しました。
　例えば、もし15マス選んだ時点で✔️が１つも付いていない次数２の clique があった時、16個目のマスを選んでもしょーがないですよね。
　その clique からマスを２個選ばなきゃ複数解が確定してしまうのに、１個しか選べないですもんね。
　だから、その場合は15個目のマスを取り消して改めて別のマスを15個目に選ぶ。
　こういうことができるわけです。
　12マス選んだ時点で✔️が１つも付いていない次数５の clique があった時も同様で、この場合はもっと効率が良いですよね。
　ツリー構造の探索には「バックトラック」というテクニックがありますが、ツリーの先端だけでなく途中の枝ごとバッサリ切れる。
　この時間短縮は非常に大きい！

　原論文のチームは、手順 1. で MUS を全て収集した後、重なっていない MUS 同士を合成してたくさんの clique を作って手順 2. に活用しました。
　実際は次数２〜５の clique を全部作ったので、12マス目以降の枝切りが大いに捗ったことでしょう。
　バサッと鋭い切れ味！　テレショップで大人気の高枝切りバサミも真っ青だったに違いない😅

　プログラミングの観点では、プライマリー/レプリカ方式でコンピュータ同士を連携させたりなど並列処理も取り入れたようです。
　他にもまだまだ工夫はいっぱい施されました。
　なんせ54億個もの完成図が相手ですもんね。効率化は大事です。

6-2．ヒッティングセット問題

　最後は、数学色の強い話。
　とは言っても、うわべだけをちょろっと話して終わりです。

　セクション５のマス選びに関連して、原論文の中には「hit」という単語が割と目立ちます。
　これは「ヒッティングセット問題 (hitting set problem)」と関連が深いからなんです。
　寡聞にして私はその問題を知りませんでしたが、集合論やグラフ理論などに詳しい方々なら「集合被覆問題」「頂点被覆問題」などの問題を既に思い出していたかもしれません。

　全体集合として有限集合 \(U\) があり、\(U\) の部分集合 \(S_1,\ S_2,\ \cdots,\ S_n\) が与えられたとする。
　この時、全ての \(S_k\ (k=1, 2, \cdots, n)\) に対して \(S_k \cap H=\emptyset\)（\(\emptyset\) は空集合）となるような集合 \(H\) は見つかるだろうか？
　ただし、\(H\) の要素数は \(p\) であるとする。

　「どの集合 \(S_1, \ S_2,\ \cdots,\ S_n\) にも交差する集合 \(H\) を作る」という作業をするわけですね。
　実は、この作業はセクション５のマス選びと同じなんです。

  • 集合 \(U\) はナンプレ完成図。
  • 集合 \(S_1,\ S_2,\ \cdots,\ S_n\) は MUS 達（ \(n\) は MUS の個数）。
  • 集合 \(H\) はヒント数字として選ばれたマス達。
  • 16マス選ぶことを想定しているので、\(p=16\)。

　\(H\) が各 \(S_k\) に交差することを「\(H\) は \(S_k\) にヒットする」と言い、\(H\) 自身を「ヒッティングセット」と言います。
　セクション５では、作成したヒッティングセットをそのまま問題図にして唯一解を検証していったんですね。
　16ヒントナンプレ問題の解決にヒッティングセット問題が直接役立ちました。

　このヒッティングセット問題、数学以外の分野にもいくつかの応用があるようですね。
　原論文にも例が載っています。

Such situations occur in bioinformatics (gene expression analysis), software testing as well as computer networks, and when finding optimal drug combinations; the last of these papers lists protein network discovery, metabolic network analysis and gene ontology as further areas in which hitting set problems naturally arise. Besides, our algorithm can be applied to the hypergraph transversal problem, which appears in artificial intelligence and database theory.
原論文 p.4 より

　バイオインフォマティクスとか遺伝子オントロジーとか私には完全に未知の世界ですが、ヒッティングセットは非常に有用な概念なんだろうなとは伝わってきます。
　探せば他にも応用はあるかもしれませんね。

参考・参照

更新履歴