BUG+1：なぜ答えが1つだけという前提が必要？

候補が3つのマスを1つ見つければよい？

BUG+1は、答えが1つだけのパズルで、ほぼすべての空きマスに候補が2つある特別な状態を利用します。ただし、「候補が3つのマスが1つあり、残りは2つ」という見た目だけでは不十分です。行・列ごとに数字が現れる回数も確認する必要があり、何よりも答えが1つだけという前提が必要です。

解の一意性は、行・列・3×3ブロックに1から9までを1回ずつ入れるルールとは別のものです。そのルールをすべて守る完成盤面が、2つ以上ある場合もあります。自分で入力した盤面やヒント数字を消した盤面では、解の一意性を先に確認しましょう。

使える条件 — 前提からマスの数、行・列ごとの回数まで

1. 現在の盤面の解が一意で、これまでに入れた数字や消した候補も正しい必要があります。
2. ちょうど3つの候補がある空きマスは1つだけで、残りのすべての空きマスには候補がちょうど2つなければなりません。
3. 候補が3つのマスから数字を1つ仮に消したとき、残る各候補数字が、それが現れるすべての行・列・ブロックでちょうど2回ずつ現れる必要があります。すでに埋まっている数字は、候補として現れる回数が0です。
4. したがって、消す前のその数字は、特別なマスが属する行・列・ブロックのそれぞれで3回現れます。1本の行・列で3回と数えただけで、確認を終えてはいけません。

このように、すべての空きマスに候補が2つずつあり、行・列ごとの出現も2回ずつである状態をBUGと呼びます。その状態に解があるなら、選択を反転させた別の解もあるので、解が1つだけということはありえません。解がない可能性もあります。解が一意の盤面では、その状態をそのまま残せないので、BUGを崩す追加の候補1つを特別なマスに入れます。

例題 — r7c6の追加候補はどれ？

c1c2c3c4c5c6c7c8c9

r1r2r3r4r5r6r7r8r9

68

7

36

89

5

1

39

4

2

9

1

5

2

4

3

7

8

6

28

4

23

7

6

89

39

5

1

4

2

8

69

3

69

5

1

7

5

6

9

4

1

7

2

3

8

1

3

7

58

2

58

4

6

9

3

8

26

56

7

256

1

9

4

7

9

1

3

8

4

6

2

5

26

5

4

1

9

26

8

7

3

★

★ r7c6の候補は2, 5, 6です。ほかの空きマスは、すべて候補が2つだけです。数字6の位置を数えてみましょう。

• 7行目：r7c3, r7c4, r7c6の3マスです。
• 6列目：r4c6, r7c6, r9c6の3マスです。
• 8番ブロック：r7c4, r7c6, r9c6の3マスです。

r7c6の6を除くと、この3つの領域でも6の場所が2か所ずつ残り、ほかのすべての候補が行・列ごとに現れる回数も0または2になります。この盤面は、バックトラッキングで解が1つであることを確認済みです。したがって、r7c6=6です。2や5を入れると、解が一意であるという前提と両立しません。確定したあとは、同じ行・列・ブロックの6の候補を消し、基本の解き方に戻ります。

使えない場合とよくある誤解

• 解がいくつあるか分かりません。 生成器が解の一意性を保証しているか、別途検証した盤面でのみ、この前提を使いましょう。論理ソルバーでBUG+1を有効にすること自体は、解の一意性の検査ではありません。
• 候補が3つのマスが2つ以上あります。 この記事のBUG+1の条件には当てはまりません。
• 候補の数は合っていますが、行・列ごとの回数が違います。 BUGではないので、追加の候補を確定できません。
• 候補を書き漏らしています。 間違ったメモでできたBUGの形は、根拠になりません。
• BUGなら必ず解がちょうど2つだと思います。 ここで必要なのは、解が一意にはなりえないという事実です。独立に変わる部分があれば、解はさらに多くなることがあります。

解が一意でない反例 — 同じ条件でも8を確定できません

c1c2c3c4c5c6c7c8c9

r1r2r3r4r5r6r7r8r9

8

7

6

9

5

1

3

4

2

9

1

5

2

4

3

78

78

6

2

4

3

7

6

8

9

5

1

4

2

8

6

3

9

5

1

7

5

6

9

4

1

7

2

38

38

1

3

7

8

2

5

4

6

9

3

8

2

5

7

6

1

9

4

7

9

1

3

8

4

6

2

5

6

5

4

1

9

2

78

378

38

★

この反例は、生成器の完成盤面からヒント数字を消し、論理的な手順で整理して見つけました。候補が3つのマスはr9c8だけで、追加の候補に見える数字は8です。9行目ではr9c7・r9c8・r9c9、8列目ではr2c8・r5c8・r9c8、9番ブロックではr9c7・r9c8・r9c9に、8が3回ずつ残っています。ほかの候補が現れる回数も0または2なので、解の一意性を除くBUG+1の候補条件は、すべて満たしています。

しかし、解の個数を検査した結果は2つ以上です（検査器は2つ見つけると停止します）。解の一意性を確認せずにBUG+1を有効にすると、ソルバーはr9c8=8を提案します。次の2つの埋め方も、どちらも行・列・ブロックのルールを守っているので、その確定は必須ではありません。次の7マス以外は、図の数字をそのままにします。

空きマス	埋め方A	埋め方B
r2c7	7	8
r2c8	8	7
r5c8	3	8
r5c9	8	3
r9c7	8	7
r9c8	7	3
r9c9	3	8

r9c8は、Aでは7、Bでは3です。したがって、「r9c8は必ず8」という結論は誤りです。8になる解も存在しますが、可能な解を1つ選んだことと、すべての解で成り立つ確定は別です。この反例は、解が複数あるために生じる実際の失敗であり、候補の書き漏らしによる見せかけの形ではありません。

練習問題

c1c2c3c4c5c6c7c8c9

r1r2r3r4r5r6r7r8r9

8

24

39

49

7

6

23

5

1

1

24

39

5

49

8

7

6

23

5

6

7

3

1

2

4

9

8

6

9

5

2

3

1

8

4

7

7

3

1

8

6

4

9

2

5

2

8

4

7

5

9

1

3

6

39

7

2

49

8

5

6

1

34

39

5

6

1

49

7

23

8

234

4

1

8

6

2

3

5

7

9

★

★ r8c9の候補は2, 3, 4です。この盤面も解は一意です。どの候補を入れればよいでしょうか？ 3回現れる3つの領域を、座標で書いてみましょう。

答えを見る

r8c9=3です。8行目の3はr8c1, r8c7, r8c9、9列目の3はr2c9, r7c9, r8c9、9番ブロックの3はr7c9, r8c7, r8c9にあります。r8c9の3を除くと、ほかの空きマスを含むすべての候補が、それぞれの現れる領域で2回ずつ残ります。解が一意であるという前提から、そのBUG状態を避ける必要があるので、追加の候補3を入れます。

続けて読む

前提知識は候補数字の書き方とナンプレに試行錯誤は必要？です。次に、AIC入門：強リンクと弱リンクを交互につなぐと、何を消せる？を読んでみましょう。

例題の盤面は、sudoku-coreの生成器と論理ソルバーを使って見つけた自作の盤面です。シード・難易度・手順番号はメタデータに記録しています。定義の参考：HoDoKu Uniqueness。