Number Place（9×9数字配置）の解き方 — 上級編: 仮置きを入れ子にして、奥で矛盾を見つける

出題と、naked/hidden singleだけで確定する範囲

この盤面は次の数字で出題されます(.は空欄、56マスが空き、levelForBlanks(56)は'hard'、mediumの閾値54を超えています)。

. . . | . 8 2 | 4 . .
. . . | 9 . 1 | 3 . .
. . . | . . . | . 5 9
------+-------+------
. 7 . | 6 4 . | . 3 .
. . . | 1 . . | . . 8
. . . | . . 7 | . . 2
------+-------+------
9 . . | . 7 8 | . . 5
5 . 1 | . . . | . . .
2 . . | 4 . . | . 9 .

初級編・中級編と同じ手順(naked single→hidden singleの繰り返し)を適用すると、81マス中56マス(69%)が確定し、25マスが未確定のまま残ります(この記事のために実装したスクリプトで実行して確認)。この時点の盤面は次のとおりです。

7 . . | 5 8 2 | 4 1 6
4 . . | 9 6 1 | 3 . 7
1 . . | 7 3 4 | . 5 9
------+-------+------
8 7 2 | 6 4 9 | 5 3 1
6 . . | 1 2 3 | . . 8
3 1 . | 8 5 7 | . . 2
------+-------+------
9 . . | . 7 8 | 1 . 5
5 . 1 | . 9 6 | . . 4
2 . 7 | 4 1 5 | . 9 3

これ以上、naked/hidden singleだけを繰り返しても、この25マスの候補はこれ以上絞れません。

1回の仮置きでは終わらない

中級編と同じように、未確定のマスの中から候補が最も少ないマスを選んで仮置きします。この盤面で最初に候補が絞られているのは行1列2で、候補は{3, 9}の2択です。

「行1列2 = 3」と仮に決めてnaked/hidden singleを波及させると、6マスが新たに確定しますが、その先で行8列8が候補0個になり矛盾します(詳しくは次の節)。もう一方の「行1列2 = 9」も試すと、こちらは矛盾しませんが、波及が1マス(行1列3=3)で止まり、まだ大部分(23マス)が未確定のまま残ります。ここが中級編との違いです。中級編では1回の仮置きで残り全部が確定しましたが、この盤面では確定しません。

そこで、「行1列2 = 9」という1回目の仮置きを維持したまま、次に候補が絞られたマス(行2列3、候補{5, 8})についてさらに仮置きを重ねます。このように、1つの仮置きの中でさらに仮置きを重ねる操作を「入れ子の仮置き」と呼びます。

実際に検証した4通り

2段の仮置き(行1列2に{3, 9}、行2列3に{5, 8})の組み合わせは4通りです。この記事のために実装したスクリプトで、4通りすべてを最後まで検証すると、そのうち3通りが矛盾、1通りだけが正解でした。

① 行1列2 = 3 → 矛盾(6マスの波及後、行8列8が候補0個)
① 行1列2 = 9(波及は1マスで停止、23マス未確定のまま)
  ├─② 行2列3 = 5 → 完成(残り22マスすべてnaked/hidden singleで確定、答えと一致)
  └─② 行2列3 = 8 → 矛盾(5マスの波及後、行9列7が候補0個)

正解にたどり着く組み合わせは、①行1列2=9・②行2列3=5です。②が決まった時点で、残る22マスは仮置きなしにnaked/hidden singleだけですべて確定しました。

矛盾の詳細(1): 行1列2 = 3

1. 仮定: 行1列2 = 3
2. naked single: 行1列3=9 → 行6列3=4 → 行6列8=6 → 行7列8=2 → 行8列2=8 → 行8列7=7(この順で6マスが確定)
3. この状態で行8列8を確認します。行8にすでに入っている数字は5,8,1,9,6,7,4(7個、うち8は手順2で確定した行8列2=8、7は行8列7=7)で、残りは{2,3}のはずです。一方、列8にはすでに1,5,3,6,2,9(6個、うち6は手順2の行6列8=6、2は行7列8=2)が入っており、列の残りは{4,7,8}です。行が要求する{2,3}と、列が許す{4,7,8}には共通の数字が1つもなく、候補が0個になります(3×3ブロックまで確認するまでもなく、行と列だけで矛盾が確定します)。

この時点で矛盾が確定します。したがって、行1列2 = 3という仮定は誤りです。

矛盾の詳細(2): 行1列2 = 9 & 行2列3 = 8

1. 仮定: 行1列2 = 9(この時点で波及は行1列3=3の1マスのみ)
2. 仮定: 行2列3 = 8
3. naked single: 行2列8=2 → 行3列3=6 → 行3列7=8 → 行7列3=4 → 行7列8=6(この順で5マスが確定)
4. 行9列7を見ると、行9にすでに入っている数字は2,7,4,1,5,9,3(7個)で、残りは{6,8}のはずです。しかし、このマスが属する列7を見ると、すでに4,3,8,5,1が入っており、列の残りは{2,6,7,9}です。行と列の共通部分は{6}だけに絞られますが、さらにこのマスが属する3×3ブロック(行7〜9・列7〜9)を見ると、すでに1,6,5,4が入っており、ブロックにはすでに6が使われています。行・列が要求する6が、ブロックではすでに使用済みのため、候補が0個になります。

この時点で矛盾が確定します。したがって、行1列2=9のもとで行2列3=8という仮定も誤りです。

正解: 行1列2 = 9 & 行2列3 = 5

残る組み合わせ「行1列2=9・行2列3=5」で確定し直したうえで、naked/hidden singleを波及させると、今度は矛盾なく残り22マスすべてが確定します。完成形は次のとおりです。

7 9 3 | 5 8 2 | 4 1 6
4 2 5 | 9 6 1 | 3 8 7
1 6 8 | 7 3 4 | 2 5 9
------+-------+------
8 7 2 | 6 4 9 | 5 3 1
6 5 9 | 1 2 3 | 7 4 8
3 1 4 | 8 5 7 | 9 6 2
------+-------+------
9 4 6 | 3 7 8 | 1 2 5
5 3 1 | 2 9 6 | 8 7 4
2 8 7 | 4 1 5 | 6 9 3

この完成形は各行・各列・各3×3ブロックに1〜9が過不足なく1回ずつ現れ、E.generateが実際に持っていた完成盤(answer)と1マスの違いもなく一致します(実行して確認済み)。

誤りやすい判断

• 1回仮置きして矛盾が出ないからといって、それだけで確定とは限らない。 中級編までの感覚のまま「1回仮置きして波及が止まらなければ正解」と判断すると、この実例(行1列2=9)のように未確定のマスがまだ23個残っている状態を見落とします。波及後に未確定のマスが0個になっているかを必ず確認してください。
• 矛盾は、複数マス先の波及を経て、複数の行・列・ブロックの情報が積み重なって初めて見える。 矛盾の詳細(1)では、6マス波及させて初めて行8列8で行と列の食い違いが判明しました。1〜2マス先で矛盾が出ないからと安心せず、波及が止まるところまで進めてください。
• 入れ子の仮置きは、内側の仮置きが矛盾しても、外側の仮置きが自動的に正しいとは限りません。 この実例では外側(行1列2=9)の下でも、内側(行2列3)の2通りのうち1通り(=8)が矛盾しました。外側の仮置きが正しいと分かるのは、内側の候補を1つずつ確認し尽くして初めて言えることです(この実例ではたまたま外側の最初の選択肢(=3)自体も矛盾でしたが、これは実例固有の結果です)。

読者の検証方法

• 同じ盤面はシード"scan-hard-6"・難易度"hard"で再現できます(E.generate('scan-hard-6', 'hard'))。
• 手元でメモ入力モードを使い、naked/hidden singleで確定する56マスを先に埋めたうえで、行1列2に3を仮に入力すると、本文の手順2と同じ6マスが確定した後、行8列8が矛盾する(行の残り{2,3}と列の残り{4,7,8}が噛み合わない)ことを確認できます。
• 「一手戻す」で行1列2の入力を取り消し、今度は9を入力してから行2列3に8を試すと、本文の矛盾の詳細(2)と同じ5マス波及後に行9列7が矛盾することを確認できます。
• 不安な場合は、仮置きを1つ試すたびに「1マスのヒント」で答え合わせしながら進めても、手順の妥当性は変わりません(ヒントを使うとレート記録の対象外にはなります)。

この記事が確認していないこと

• 「naked/hidden singleで56マス確定した後、2段の仮置き(2×2=4通り)で解ける」という具体的な展開は、この記事の実例(このシード)固有のものです。README・コードのいずれにも「hard相当の問題は仮置き2段で解ける」という基準は明記されておらず、別のhard盤面で同じ深さになることは保証されません(3段以上の入れ子が必要なhard盤面が存在する可能性を、この記事は否定していません)。
• 仮置きを重ねる順番(どのマスを先に選ぶか)によって、矛盾までの手数や必要な入れ子の深さが変わりうるかどうかは、この記事の範囲では検証していません。この記事はいずれも候補が最も少ないマスを優先して選ぶ方式(MRV)で進めています。
• より深い入れ子(3段以上)を要する盤面については、今回検証した範囲では確認していません。