【ナンプレ】Naked(N国同盟)とHidden(隠れN国同盟)は同じ
ナンプレのルール
・9×9のマスに1～9の数字を入れる
・3×3のブロックで区切られている
・行、列、ブロック内で同じ数字が入ってはいけない
・解は一つ
「ルールが分からない」という方は、実際に遊んでみて下さい。
タイトルにもある「N国同盟」「隠れN国同盟」とは、ナンプレの解き方の一つです。
N国同盟とは
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| A | 8 | 4 | 9 | 1,2 | 5 | 6 | 1,2 | 3 | |
| B | 7 | ||||||||
| C |
例えば、上の盤面を見てください。
同じ行、同じ列、同じブロックの数字は入らないので、A1には1,2,8のどれかが入ります。
ここで、A4,A7を見てみると、1,2のどちらかが入ります。
なので、A1には1,2は入らず、残った8が入る、という考え方です。
この場合、1,2と候補が二つあるので「二国同盟」と言われています。
英語では候補を洗い出すとと露わになる様子から「Naked Pairs」と言われています。
（N国同盟は、自然数NとN国党が由来です。N国党は名前だけ借りたので深い意味はありません。自分が勝手に名付けました。）
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| A | 8 | 4 | 9 | 1,2,3 | 5 | 6 | 1,2 | 2,3 | |
| B | 7 | ||||||||
| C |
上記の場合は候補が1,2,3と三つあるので「三国同盟」となります。
英語名は「Naked Triples」です。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| A | 8 | 4 | 9 | 1 | 5 | 6 | 2 | 3 | |
| B | 7 | ||||||||
| C |
N=1の時は「単一候補」と言い、英語名は「Naked Single」となります。
日本語だと「国同盟」が消えてしまいますが、英語の場合は「Naked」が残ります。
今回の証明はN=1の場合も含むので、英語名の「Naked」の方が適当です。
隠れN国同盟とは
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| A | 3,4,5 | 3,4,5 | 9 | 1,2 | 7 | 6 | 1,2,3 | 1,2,3 | 8 |
| B | 1 | 6 | |||||||
| C | 2 | 7 | 8 | 3 |
例えば、上の盤面を見てください。
A行の中で、4,5が使われているのはA1,A2のみなので、A1,A2に4,5のどちらかが入ります。
同じブロックには同じ数字は入らないので、C3には4,5は入らず、8が入ります。
この場合、4,5と候補が二つあるので「隠れニ国同盟」と言います。
4,5は、候補を全て洗い出しても他の候補に隠れて見えにくいのが特徴です。
英語では「Hidden Pairs」と言います。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| A | 3,4,5,9 | 3,4,5,9 | 3,4,5,9 | 1,2 | 7 | 6 | 1,2,3 | 1,2,3 | 8 |
| B | 1 | 6 | |||||||
| C | 2 | 7 | 8 | 3 |
上記の場合は候補が4,5,9と三つあるので「隠れ三国同盟」となります。
英語名は「Hidden Triples」です。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| A | 4 | 3,5 | 9 | 1,2 | 7 | 6 | 1,2,3 | 1,2,3 | 8 |
| B | 1 | 6 | |||||||
| C | 2 | 7 | 3 |
N=1の時は「隠れ単一候補」と言い、英語名は「Hidden Single」となります。
上記の場合、A行で5が使われているのはA2のみなので、A2=5が確定します。
N国同盟と隠れN国同盟の同値性 概要
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| A | 3,4,5,9 | 3,4,5,9 | 3,4,5,9 | 1,2 | 7 | 6 | 1,2,3 | 1,2,3 | 8 |
| B | 1 | 6 | |||||||
| C | 2 | 7 | 8 | 3 |
上記はA1,A2,A3の「隠れ三国同盟」と言いましたが、A4,A7,A8の「三国同盟」として捉えてもよいです。
隠れN国同盟は見つけにくいため、隠れN国同盟は使わなくてもナンプレは解けるよという主張です。
ただし、隠れN国同盟を使用すると9-5=4なので、四国同盟が最大数となりますが、隠れN国同盟を使用しないと八国同盟が最大数となる、というリスクはあります。
N国同盟と隠れN国同盟の同値性 証明
※ここからは数学になるので、パズルだけを楽しみたい方は読み飛ばしても結構です。
$$U=\lbrace 1,2,...,9 \rbrace（行、列、ブロックのいずれか）$$
$$C_{1},...,C_{9} \subset U, |C_1|=...=|C_9|=1, s≠t ⇒ C_{s} ≠ C_{t}（行、列、ブロックの各マス）$$
$$x_1,...,x_9 \in \lbrace 1,2,...,9 \rbrace, s≠t ⇒ x_{s} ≠ x_{t}（マスに入る数）$$
$$1 ≤ n ≤ 8（何国同盟か）$$
$$1 ≤ i_{1},...,i_{9} ≤ 9, s≠t ⇒ i_{s} ≠ i_{t}$$
マスの数と、それらのマスが含む候補の総数が一致すればよいので
$$∃C_{i_{1}},...,C_{i_{n}} \subset U s.t. \bigcup_{k = 1}^n C_{i_{k}} = \lbrace x_1,...,x_n \rbrace$$
$$例：n=3のとき$$
$$∃C_2,C_3,C_5 \subset U s.t. C_2 \cup C_3 \cup C_5 = \lbrace 3,4,8 \rbrace$$
これは3,4,8の三国同盟である
マスの数と、それらのマスだけが含む候補の総数が一致すればよいので
$$∃C_{i_{1}},...,C_{i_{n}} \subset U s.t. x_1,...,x_n \in \bigcup_{k = 1}^n C_{i_{k}}, x_1,...,x_n \notin \bigcup_{k = n+1}^9 C_{i_{k}}$$
$$例：n=4のとき$$
$$∃C_2,C_4,C_6,C_8 \subset U s.t. 1,6,8,9 \in C_2 \cup C_4 \cup C_6 \cup C_8,$$
$$1,6,8,9 \notin C_1 \cup C_3 \cup C_5 \cup C_7 \cup C_9$$
これは1,6,8,9の隠れ四国同盟である
方針
N国同盟が成立している時は、他のマスで隠れN国同盟が成立し、隠れN国同盟が成立している時は、他のマスでN国同盟が成立していることを示す。
Naked$⇒$Hidden
$\bigcup_{k = 1}^n C_{i_{k}} = \lbrace x_1,...,x_n \rbrace, \bigcup_{k = 1}^9 C_{i_{k}} = \lbrace x_1,...,x_9 \rbrace$より
$$x_{n+1},...,x_9 \in \bigcup_{k = n+1}^9 C_{i_{k}}, x_{n+1},...,x_9 \notin \bigcup_{k = 1}^n C_{i_{k}}$$
$B_{j_{1}}=C_{i_{9}}, B_{j_{2}}=C_{i_{8}},..., B_{j_{9}}=C_{i_{1}}$
$y_1=x_9, y_2=x_8,..., y_9=x_1$
とおき、$m=9-n$とすると
$B_{j_{m}}=C_{i_{n+1}}, B_{j_{m+1}}=C_{i_{n}}, y_m=x_{n+1}$
よって
$$y_1,...,y_{m} \in \bigcup_{k = 1}^m B_{j_{k}}, y_1,...,y_{m} \notin \bigcup_{k = m+1}^9 B_{j_{k}}$$
これはHiddenの定義である
Hidden$⇒$Naked
$x_{1},...,x_n \notin \bigcup_{k = n+1}^9 C_{i_{k}}, \bigcup_{k = 1}^9 C_{i_{k}} = \lbrace x_1,...,x_9 \rbrace$より
$$\bigcup_{k = n+1}^9 C_{i_{k}} = \lbrace x_1,...,x_9 \rbrace - \lbrace x_1,...,x_n \rbrace = \lbrace x_{n+1},...,x_9 \rbrace$$
Naked$⇒$Hiddenの場合と同様の対応づけをすると
$$\bigcup_{k = 1}^m B_{j_{k}} = \lbrace y_{1},...,y_{m} \rbrace$$
となり、これはNakedの定義である
まとめ
Naked(N国同盟)とHidden(隠れN国同盟)は同じ意味であり、どちらかしか使えなくても解けます。
解き方を複数覚えるのは大変だ、という方はどちらかに絞ってはいかがでしょうか？