0

【ナンプレ】BoxLineとPointingPairは同じ

31
0
$$$$

ナンプレのルール
・9×9のマスに1~9の数字を入れる
・3×3のブロックで区切られている
・行、列、ブロック内で同じ数字が入ってはいけない
・解は一つ

タイトルにもある「BoxLine」「PointingPair」とは、ナンプレの解き方の一つです。

関連リンク
【ナンプレ】Naked(N国同盟)とHidden(隠れN国同盟)は同じ

BoxLineとは

123456789
A634,8,92
B5731,2,8,91,2,8,91,2,8,98,964
C574,8,9
D1

例えば、上の盤面を見てください。

同じ行、同じ列、同じブロックの数字は入らないので、B7には8,9のどちらかが入ります。

そして、B4,B5,B6のいずれかに1,2が入ります。

すると、同じブロックであるA6,C6に1,2は入らなくなります。

これがBoxLineです。

PointingPairとは

123456789
A632
B57364
C(2)(2)(2)571,4,8,9

例えば、上の盤面を見てください。

A8に2が埋まっています。

すると、同じ行であるA1,A2,A3に2は入らず、C1,C2,C3のいずれかに2が入ることがわかります。

そして、C行ではC1,C2,C3以外には2が入らず、C6に2は入らなくなります。

これがPointingPairです。

123456789
A63821
B57364
C(1,2,8)(1,2,8)(1,2,8)4,5,7,94,5,7,94,5,7,9

上記のように3つの数字に対して適用できる場合もあります。

123456789
A(1)(1)(1)634,8,92(1)
B5731,2,8,91,2,8,91,2,8,98,964
C(12)(12)(12)574,8,9(1)(1)
D1

上記の1のように、2つの行(列)に対して適用できる場合もあります。

もしA6に1が入った場合、A1,A2,A3,A9に1が入ることができず、C行に1が2つ存在することになり矛盾します。

よって、A6に1は入りません。

C6についても同様です。

BoxLineとPointingPairの同値性 概要

123456789
A634,8,92
B5731,2,8,91,2,8,91,2,8,98,964
C574,8,9
D1

上記は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}(マスに入る数)$$

BoxLine

ある数が縦(横)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である。

PointingPair

あるボックス内で、ある数が縦(横)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の定義である

列の場合も同様

投稿日:2023118

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

あーく
あーく
104
135947
使える数学、面白い数学の分かりやすい解説を心がけています。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中