Number Place（9×9数字配置）の解き方 — 中級編: naked/hidden singleで止まったら、1マスだけ仮に決めて矛盾を探す

まずnaked single・hidden singleで絞れるところまで絞る

初級編で扱ったnaked singleに加えて、この記事ではhidden singleという技法も使います。hidden singleとは、「ある行(または列、または3×3ブロック)の中で、まだ数字が入っていないマスのうち、特定の数字vを候補として持てるマスが1個しかない」場合、そのマスをvで確定する、という技法です。そのマス自身の候補が2個以上あっても、周りのマスがどれもvを候補に持てなければ、hidden singleとして確定できます。

出題時点の数字配置は次のとおりです(.は空欄、50マスが空き、levelForBlanks(50)は'medium'、閾値はeasy45以下・medium54以下)。

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

naked single・hidden singleを交互に繰り返し適用すると、81マス中21マスが次の順で確定します(nakedはnaked single、hidden-行/列/ブロックはどの単位で確定したhidden singleかを示します)。

naked      行8列1=4     naked      行9列4=5     hidden-行   行1列9=3
naked      行8列9=8     naked      行9列7=4     naked      行7列9=9
naked      行7列8=3     naked      行8列8=2     hidden-列   行2列8=9
hidden-列   行3列1=2     hidden-行   行3列3=9     hidden-列   行1列3=4
hidden-行   行1列1=1     naked      行7列1=5     hidden-行   行3列7=7
naked      行2列7=1     naked      行3列9=5     naked      行4列9=1
naked      行5列7=8     hidden-行   行6列8=4     hidden-行   行7列3=1

内訳はnaked singleが12マス、hidden singleが9マスです。この時点(21手目)の盤面は次のとおりです。

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

残る29マスは、naked single・hidden singleのどちらを繰り返しても、これ以上確定しません(実際にNode.js上でさらに数巡試しましたが、状態は変化しませんでした)。これがnaked/hidden singleだけでは解けない局面です。

1マスを仮に数字で決めて波及させる

未確定の29マスの中から、行1列2に注目します。このマスの候補は、行1にすでに入っている数字(1,4,9,7,2,8,3、7個)を除いた{5,6}のうち、列2にすでに入っている数字(3,4,1,9,2)にも、このマスが属する3×3ブロック(行1〜3・列1〜3)にすでに入っている数字(1,4,8,2,3,9)にも5・6のどちらも含まれないため、候補は{5,6}の2択です(全81マスの中で最も候補が少ないマスの1つです)。

この2択のうち、「行1列2 = 5」と仮に決めて、naked single・hidden singleを波及させます。

1. 仮定: 行1列2 = 5
2. naked single: 行1列6 = 6 / 行2列5 = 5 / 行6列5 = 2 / 行4列5 = 6 / 行6列3 = 5 / 行8列5 = 3 / 行4列2 = 8 / 行4列3 = 2 / 行5列3 = 6 / 行7列2 = 7 / 行7列6 = 8(この順で11マスがnaked singleとして次々に確定します)
3. この時点で行8列3を見ると、行8にすでに入っている数字は4,9,3,1,5,2,8(7個)で、残りは{6,7}のはずです。しかし、**このマスが属する3×3ブロック(行7〜9・列1〜3)にはすでに1,7,5,4,9,6,2**が入っており、ブロックの残りは{3,8}しかありません。行が要求する{6,7}と、ブロックが許す{3,8}には共通の数字がなく、候補が0個になります。

行・列・ブロックのどの単位で見ても、あるマスに入れられる数字が1つもない状態は、Number Placeのルール(各行・各列・各ブロックに1〜9が1回ずつ)そのものと矛盾します。したがって、手順1の仮定(行1列2 = 5)は誤りで、正しくは「行1列2 = 6」です。

仮定をひっくり返すと、残り全部がnaked singleだけで決まる

「行1列2 = 6」で確定し直したうえで、naked single・hidden singleを再び波及させると、今度は矛盾なく残り28マスすべてがnaked singleだけで確定します(hidden singleは1回も必要ありませんでした)。完成形は次のとおりです。

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

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

なぜnaked/hidden singleの繰り返しだけでは見抜けないのか

naked single・hidden singleは、どちらも「その1マス」または「その1つの行・列・ブロック」だけを見て判定します。行1列2を仮に5と決めても、決めた瞬間にはどの行・列・ブロックとも矛盾しません(だからこそ、この2つの技法だけでは81マス中50マスまでしか進めませんでした)。矛盾が表面化するのは、その仮定から11マス先まで波及させて、行8のnaked singleの積み重ねと、行8列3が属するブロックの情報が突き合わさったときです。この記事の実例では、行1列2から始まった連鎖が11マス分の確定を経て初めて、行とブロックの食い違いが判明しました。

手順のまとめ

1. naked single・hidden singleで絞れるところまで絞る(この実例では81マス中21マス)。
2. 残ったマスの中から候補が最も少ないマス(この実例では候補2個)を選び、仮に一方の数字で決める。
3. 同じ2つの技法(naked single・hidden single)を波及させる。
4. 波及の途中で、ある行・列・ブロックのいずれかで、まだ埋まっていないマスの候補が0個になる場合、その仮定は誤り。もう一方の数字に決め直して手順3をやり直す。
5. 矛盾が起きなければ、そのまま波及させて残りを埋める。

誤りやすい判断

• 仮定した直後に矛盾が出ないからといって、その仮定が正しいとは限らない。 この記事の実例では、矛盾が判明するまでに11マス分の波及が必要でした。1〜2マス先で矛盾が出ないからと安心せず、波及が止まるところまで進めてください。
• 候補0個の矛盾は、行・列・ブロックのどれか1つだけを見ていては気づけないことがある。 この記事の実例(行8列3)では、行だけ見れば{6,7}の2択に見え、矛盾には見えません。行・列・ブロックの3つすべてを突き合わせて、初めて候補が0個だと分かります。
• どのマスを仮定に選ぶかは、この記事の手順の正しさに影響しません。 未確定の29マスのうちどれを最初に仮定しても、正しい方の数字を選べば最終的には同じ完成形にたどり着きます(候補が少ないマスから選ぶと、矛盾までの手数が短くなる傾向があります)。
• 仮定は「賭け」ではなく、UIの「一手戻す」で安全に試せる操作です。 仮に数字を入れてみて矛盾が見えたら、「一手戻す」を繰り返して入力を取り消し、逆側を試せます。メモ入力モードを使えば、確定前の候補として書き留めることもできます。

読者の検証方法

• 同じ盤面はシード"scan-medium-49"・難易度"medium"で再現できます(E.generate('scan-medium-49', 'medium'))。
• 実際にプレイする場合は、まずメモ入力モードでnaked/hidden singleの21マスを埋め、行1列2に5と6のメモを残したうえで、片方を仮に本入力してみると、この記事と同じ展開を自分の手元で確認できます。
• 不安な場合は、仮定を1つ試すたびに「1マスのヒント」で答え合わせしながら進めても、手順の妥当性は変わりません(ヒントを使うとレート記録の対象外にはなります)。
• この記事の手順自体は、Node.js上でこの記事のために実装したスクリプト(候補計算はnumberplace/engine.jsと同じビット演算)を実行し、矛盾の発生箇所・完成形をE.generateのanswerと突き合わせて確認しました。

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

• 「未確定のマスが29個残ったら、1回の仮定と11マス分の波及で解ける」という具体的な展開は、この記事の実例固有のものです。README・コードのいずれにも「medium相当の問題は仮定1回で解ける」という基準は明記されておらず、別のmedium盤面で同じ手数になることは保証されません。
• 上級編(その3)で扱う、1回の仮定では終わらず、仮定の上にさらに仮定を重ねる必要があるケースは扱っていません。