【ナンプレ】BoxLineとPointingPairは同じ
ナンプレのルール
・9×9のマスに1～9の数字を入れる
・3×3のブロックで区切られている
・行、列、ブロック内で同じ数字が入ってはいけない
・解は一つ
タイトルにもある「BoxLine」「PointingPair」とは、ナンプレの解き方の一つです。
関連リンク
【ナンプレ】Naked(N国同盟)とHidden(隠れN国同盟)は同じ
BoxLineとは
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| A | 6 | 3 | 4,8,9 | 2 | |||||
| B | 5 | 7 | 3 | 1,2,8,9 | 1,2,8,9 | 1,2,8,9 | 8,9 | 6 | 4 |
| C | 5 | 7 | 4,8,9 | ||||||
| D | 1 |
例えば、上の盤面を見てください。
同じ行、同じ列、同じブロックの数字は入らないので、B7には8,9のどちらかが入ります。
そして、B4,B5,B6のいずれかに1,2が入ります。
すると、同じブロックであるA6,C6に1,2は入らなくなります。
これがBoxLineです。
PointingPairとは
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| A | 6 | 3 | 2 | ||||||
| B | 5 | 7 | 3 | 6 | 4 | ||||
| C | (2) | (2) | (2) | 5 | 7 | 1,4,8,9 |
例えば、上の盤面を見てください。
A8に2が埋まっています。
すると、同じ行であるA1,A2,A3に2は入らず、C1,C2,C3のいずれかに2が入ることがわかります。
そして、C行ではC1,C2,C3以外には2が入らず、C6に2は入らなくなります。
これがPointingPairです。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| A | 6 | 3 | 8 | 2 | 1 | ||||
| B | 5 | 7 | 3 | 6 | 4 | ||||
| C | (1,2,8) | (1,2,8) | (1,2,8) | 4,5,7,9 | 4,5,7,9 | 4,5,7,9 |
上記のように3つの数字に対して適用できる場合もあります。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| A | (1) | (1) | (1) | 6 | 3 | 4,8,9 | 2 | (1) | |
| B | 5 | 7 | 3 | 1,2,8,9 | 1,2,8,9 | 1,2,8,9 | 8,9 | 6 | 4 |
| C | (12) | (12) | (12) | 5 | 7 | 4,8,9 | (1) | (1) | |
| D | 1 |
上記の1のように、2つの行(列)に対して適用できる場合もあります。
もしA6に1が入った場合、A1,A2,A3,A9に1が入ることができず、C行に1が2つ存在することになり矛盾します。
よって、A6に1は入りません。
C6についても同様です。
BoxLineとPointingPairの同値性 概要
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| A | 6 | 3 | 4,8,9 | 2 | |||||
| B | 5 | 7 | 3 | 1,2,8,9 | 1,2,8,9 | 1,2,8,9 | 8,9 | 6 | 4 |
| C | 5 | 7 | 4,8,9 | ||||||
| D | 1 |
上記はB4,B5,B6のBoxLineで捉えてもよいですし、
C1,C2,C3のいずれかが2であるPointingPairと
A行ではA1,A2,A3,A9のいずれか、C行ではC1,C2,C3,C8,C9のいずれかが1であるPointingPairの組み合わせとして捉えてもよいです。
BoxLineとPointingPairの同値性 証明
$$U=\lbrace 1,2,...,9 \rbrace（行、列、ブロックのいずれか）$$
$$C_{(1,1)},...,C_{(9,9)} \subset U, |C_{(1,1)}|=...=|C_{(9,9)}|=1$$
$$s≠t ⇒ C_{(n,s)} ≠ C_{(n,t)}, C_{(t,n)} ≠ C_{(t,n)} (同じ行(列)に同じ数字は入ってはいけない)$$
$B=\bigcup_{n = 1}^3\bigcup_{m = 1}^3C_{(i_{n}, j_{m})}$
$∀C_{(i_{n}, j_{m})}, C_{(i_{s}, j_{t})} \in B, (n,m)≠(s,t) ⇒ C_{(i_{n}, j_{m})} ≠ C_{(i_{s}, j_{t})} (同じブロックに同じ数字は入ってはいけない)$
$$x_1,...,x_9 \in \lbrace 1,2,...,9 \rbrace, s≠t ⇒ x_{s} ≠ x_{t}（マスに入る数）$$
ある数が縦(横)3マスのいずれかに含まれ、そのブロック外の同じ列(行)にはその数が含まれないブロックが存在する
$∃B \ni C_{(i_1, j_1)},C_{(i_1, j_2)},C_{(i_1, j_3)} s.t. x_1 \in C_{(i_1, j_1)}∪C_{(i_1, j_2)}∪C_{(i_1, j_3)}, x_1 \notin \bigcup_{l = 4}^9C_{(i_{1}, j_{l})}$
$または$
$∃B \ni C_{(i_1, j_1)},C_{(i_2, j_1)},C_{(i_3, j_1)} s.t. x_1 \in C_{(i_1, j_1)}∪C_{(i_2, j_1)}∪C_{(i_3, j_1)}, x_1 \notin \bigcup_{k = 4}^9C_{(i_{k}, j_{1})}$
$(s≠t ⇒ i_s ≠ i_t, j_s ≠ j_t)$
例えば、$1 \in C_{(2, 2)}∪C_{(2, 3)}∪C_{(2, 1)}, 1 \notin \bigcup_{l = 4}^9C_{(2, j_{l})}$
は、ブロック$B$内の同じ行に$1$が入り、ブロック$B$外の同行には$1$が入らないBoxLineである。
あるボックス内で、ある数が縦(横)3マスに含まれないとき、その列(行)と同じ列(行)3マスにその数が含まれないボックスが存在する
$C_{(i_1, j_1)}, C_{(i_1, j_2)}, C_{(i_2, j_1)}, C_{(i_1, j_3)}, C_{(i_3, j_1)} \in B に対し$
$x_1 \notin C_{(i_1, j_1)}∪C_{(i_1, j_2)}∪C_{(i_1, j_3)} かつ$
$∃B_1 \ni C_{(i_1, j_4)}, C_{(i_1, j_5)}, C_{(i_1, j_6)} s.t. x_1 \notin C_{(i_1, j_4)}∪C_{(i_1, j_5)}∪C_{(i_1, j_6)}$
または
$x_1 \notin C_{(i_1, j_1)}∪C_{(i_2, j_1)}∪C_{(i_3, j_1)} かつ$
$∃B_2 \ni C_{(i_4, j_1)}, C_{(i_5, j_1)}, C_{(i_6, j_1)} s.t. x_1 \notin C_{(i_4, j_1)}∪C_{(i_5, j_1)}∪C_{(i_6, j_1)}$
$(s≠t ⇒ i_s ≠ i_t, j_s ≠ j_t, k_s ≠ k_t, l_s ≠ l_t)$
例えば、$5 \notin C_{(1, 2)}∪C_{(1, 3)}∪C_{(1, 1)}$というブロック$B$と
$5 \notin C_{(1, 4)}∪C_{(1, 5)}∪C_{(1, 6)}$というブロック$B_1$があればPointingPairである。
方針
BoxLineが成立している時は、他のブロックでPointingPairが成立し、PointingPairが成立している時は、他のブロックでBoxLineが成立していることを示す。
BoxLine$⇒$PointingPair
$∃B \ni C_{(i_1, j_1)},C_{(i_1, j_2)},C_{(i_1, j_3)} s.t. x_1 \in C_{(i_1, j_1)}∪C_{(i_1, j_2)}∪C_{(i_1, j_3)}, x_1 \notin \bigcup_{l = 4}^9C_{(i_{1}, j_{l})}$
$C_{(i_1, j_4)},C_{(i_1, j_5)},C_{(i_1, j_6)} \in B_1, C_{(i_1, j_7)},C_{(i_1, j_8)},C_{(i_1, j_9)} \in B_2$ とすると
$C_{(i_1, j_4)},C_{(i_1, j_5)},C_{(i_1, j_6)} \in B_1 に対し$
$x_1 \notin C_{(i_1, j_4)},C_{(i_1, j_5)},C_{(i_1, j_6)} かつ$
$∃B_2 \ni C_{(i_1, j_7)}, C_{(i_1, j_8)}, C_{(i_1, j_9)} s.t. x_1 \notin C_{(i_1, j_7)}∪C_{(i_1, j_8)}∪C_{(i_1, j_9)}$
これはPointingPairの定義である
列の場合も同様
PointingPair$⇒$BoxLine
$C_{(i_1, j_1)}, C_{(i_1, j_2)}, C_{(i_1, j_3)} \in B に対し$
$x_1 \notin C_{(i_1, j_1)}∪C_{(i_1, j_2)}∪C_{(i_1, j_3)} かつ$
$∃B_1 \ni C_{(i_1, j_4)}, C_{(i_1, j_5)}, C_{(i_1, j_6)} s.t. x_1 \notin C_{(i_1, j_4)}∪C_{(i_1, j_5)}∪C_{(i_1, j_6)}$
$x_1 \notin \bigcup_{k=1}^6 C_{(i_1, j_k)}$ より
$∃B_2 \ni C_{(i_1, j_7)}∪C_{(i_1, j_8)}∪C_{(i_1, j_9)} s.t. x_1 \in C_{(i_1, j_7)}∪C_{(i_1, j_8)}∪C_{(i_1, j_9)}$
これはBoxLineの定義である
列の場合も同様