数独 チェーン 考え方 - 強リンクと弱リンクを交互にたどる読み方と記法
数独のチェーンの解説には「r3c4 =8= r3c9 -8- r4c9」のような記法がよく出てくる。等号は強リンク、ハイフンは弱リンクを表し、強と弱を交互につないで両端が強リンクなら、両端の両方から見えるマスの候補を消せる。本記事では 1 本の鎖を盤面に描き、記号を 1 つずつ言葉に直して読む手順と、同じ鎖の 2 通りの書き方、鎖の種類の見分け方を示す。
記法は 3 種類の記号で読める
チェーンの解説が難しく見える原因の多くは、考え方より記法にある。記号の意味さえ押さえれば、長い鎖も左から順に読める。覚える記号は 3 種類だ。1 つ目はマスの名前で、r3c4 は 3 行 4 列のマスを表す。r は行、c は列の頭文字である。2 つ目は等号で、2 つのマスを強リンクで結ぶ。強リンクとは、2 つのうち少なくとも一方は必ず真になる関係のことだ。3 つ目はハイフンで、弱リンクを表す。弱リンクは、2 つが同時に真になることはない関係である。記号の間に挟む数字は、どの数字のリンクかを示す。つまり「r3c4 =8= r3c9」は「r3c4 と r3c9 のどちらかには必ず 8 が入る」と読み、「r3c9 -8- r4c9」は「r3c9 と r4c9 の両方に 8 が入ることはない」と読む。チェーンはこの等号とハイフンを交互に並べ、両端を等号で終えた物である。両端が等号なら、両端の両方から見えるマスにはその数字が入らない。下の表に、解説でよく見る記号をまとめた。
| 記号 | 読み方 | この記事の例 |
|---|---|---|
| r3c4 | 3 行 4 列のマス | r3c4 |
| =8= | 8 の強リンク (どちらかは必ず 8) | r3c4 =8= r3c9 |
| -8- | 8 の弱リンク (両方が 8 にはならない) | r3c9 -8- r4c9 |
| (8)r4c5 | r4c5 の候補の 8 | (8)r4c9=(8)r4c5 |
| (3=8)r4c9 | r4c9 の中の強リンク (3 でなければ 8) | (3=8)r4c9 |
| r1c6<>8 | r1c6 は 8 ではない (候補から消す) | r1c6<>8 |
等号とハイフンの使い方は、解法ソフト HoDoKu の解説頁「Chains and Loops」の記法に合わせた。
強リンクと弱リンクの見つけ方
記法を盤面に当てはめるには、どこに強リンクと弱リンクがあるかを見分けられる必要がある。基本の鎖で強リンクが生まれる場所は 2 つある。1 つは、ある行 / 列 / ブロックの中で、ある数字の候補がちょうど 2 マスに絞られている所だ。片方に入らなければ、もう片方に入るしかない。もう 1 つは、候補が 2 つだけのマスの中である。そのマスが 4 でなければ 7 だと言えるので、マスの中の 4 と 7 が強リンクで結ばれる。弱リンクはもっと多い。同じ行 / 列 / ブロックにある同じ数字の候補どうしは、候補が何マスあっても弱リンクで結ばれる。同じ数字は 1 つの行に 2 つ入らないからだ。この区別から大事な性質が 1 つ出てくる。候補が 2 マスだけの行の 2 マスは、強リンクであると同時に弱リンクでもある。したがって強リンクは弱リンクの代わりに使えるが、候補が 3 マス以上ある行の弱リンクを強リンクとして使うことはできない。定義の細部は用語集の強リンクと弱リンクの項目に譲り、以下では盤面で読み方を確かめる。
1 本の鎖を盤面で確かめる
下の盤は、自作の問題を、候補が 1 つのマスを埋める手筋と、数字の置き場が 1 つのマスを埋める手筋だけで進め、手が止まった局面である。この局面でネイキッドペアやヒドゥンペア、ポインティングペア、ボックスライン削減を当てても、消えるのはポインティングペアによる r7c4 の 1 だけで、ここで追う 8 の候補は 1 つも減らない。ここでは数字の 8 だけに注目する。8 の候補は 3 行目では r3c4 と r3c9 の 2 マスだけ、4 行目では r4c9 と r4c5 の 2 マスだけ、8 ブロック目 (下段の中央のブロック) では r9c5 と r8c6 の 2 マスだけにある。これが 3 本の強リンクになる。一方、9 列目には r1c9 / r3c9 / r4c9 / r5c9 / r8c9 の 5 マスに 8 の候補があり、5 列目にも r4c5 / r6c5 / r9c5 の 3 マスがある。候補が 3 マス以上あるので、ここは弱リンクとしてしか使えない。これらをつなぐと、8 r3c4 =8= r3c9 -8- r4c9 =8= r4c5 -8- r9c5 =8= r8c6 という鎖ができる。強、弱、強、弱、強の順に交互に並び、両端の r3c4 と r8c6 はどちらも強リンクで終わっている。両端の両方から見える空きマスは r1c6 と r7c4 の 2 つで、r1c6 は r3c4 と同じ 2 ブロック目、r8c6 と同じ 6 列目にある。このうち 8 の候補があるのは r1c6 だけなので、この鎖によって r1c6 の 8 を消せる。
- 鎖の両端 (r3c4 と r8c6)
- 鎖の途中の 4 マス
- 8 が消えるマス (r1c6)
空きマスの 8 の候補は r1c6 / r1c7 / r1c9 / r3c4 / r3c9 / r4c5 / r4c9 / r5c1 / r5c4 / r5c8 / r5c9 / r6c1 / r6c5 / r6c7 / r8c6 / r8c7 / r8c9 / r9c5 / r9c7 / r9c8 の 20 マス。強リンクは 3 行目 (r3c4 と r3c9)、4 行目 (r4c9 と r4c5)、8 ブロック目 (r9c5 と r8c6) で、弱リンクは 9 列目 (r3c9 と r4c9) と 5 列目 (r4c5 と r9c5) である。
記号を言葉に直して読む
鎖を読む時は、左端のマスが「その数字ではない」と置いてから、記号を 1 つずつ言葉に直していく。等号の所では「片方が違うなら、もう片方が真」と進み、ハイフンの所では「片方が真なら、もう片方は違う」と進む。この 2 つの読み方が交互に来るので、真と偽も交互に入れ替わる。強リンクで終わる右端では必ず「真」に着く。下の図はこの鎖を左から読んだ流れである。r3c4 が 8 でないなら、たどった先で r8c6 が 8 になる。言い換えると、r3c4 と r8c6 の少なくとも一方は必ず 8 になる。鎖は右から読んでも同じで、r8c6 が 8 でないなら r3c4 が 8 になる。r3c4 が 8 の場合と 8 でない場合のどちらでも、r1c6 は 8 でない。鎖の考え方そのものは用語集のチェーンの項目にあるので、ここでは記号の読み方だけに絞った。
r3c4 は 8 でないとする
左端を偽と置いて読み始める
=8= なので r3c9 が 8
3 行目の 8 の候補は 2 マスだけ
-8- なので r4c9 は 8 でない
r3c9 と同じ 9 列目にある
=8= なので r4c5 が 8
4 行目の 8 の候補は 2 マスだけ
-8- なので r9c5 は 8 でない
r4c5 と同じ 5 列目にある
=8= なので r8c6 が 8
8 ブロック目の 8 の候補は 2 マスだけ
r3c4 が 8 でも、8 でなくても (その時は r8c6 が 8)、r3c4 と同じブロックで r8c6 と同じ列の r1c6 には 8 が入らない。
両端が強リンクだと何が消えるか
鎖から消せる物は、両端のリンクの種類で決まる。両端が強リンクで、両端が同じ数字なら、両端の両方から見えるマスからその数字を消せる。HoDoKu の解説でも、X-Chain について「鎖の両端を両方見るマスからその数字を消せる」と書かれている。ここで誤解しやすいのは、両端のどちらか一方だけが真になると思い込むことだ。鎖が保証するのは「少なくとも一方は真」であって、両方が真のこともある。実際、この盤を最後まで解くと r3c4 と r8c6 はどちらも 8 になる。それでも r1c6 の 8 を消せるという結論は変わらない。逆に、どちらかの端が弱リンクで終わっている鎖からは何も消せない。たとえば r3c4 =8= r3c9 -8- r4c9 で止めると、言えるのは「r3c4 が 8 でなければ r4c9 は 8 でない」だけで、どのマスにも確定も消去も起きない。両端の数字が違う鎖もある。HoDoKu はこの形を AIC の第 2 型として扱い、互いに見える 2 マスが両端なら、始まりのマスから終わりの数字を、終わりのマスから始まりの数字を消せるとしている。どの形でも、まず両端が等号で終わっているかを確かめるのが読む時の最初の点検になる。
同じ鎖の 2 つの書き方
チェーンの記法には大きく 2 つの流儀があり、解説によってどちらを使うかが違う。1 つは、マスとマスの間に「=8=」や「-8-」を挟んでいく書き方で、HoDoKu は Nice Loop の記法と呼んでいる。この記事で使ってきたのはこちらである。どの数字のリンクかが記号の中に入るので、1 つの数字だけを追う鎖では読みやすい。もう 1 つは Eureka と呼ばれる書き方で、候補の数字を括弧に入れてマスの前に置き、リンクは「=」と「-」だけで表す。同じ鎖を Eureka で書くと (8)r3c4=(8)r3c9-(8)r4c9=(8)r4c5-(8)r9c5=(8)r8c6 になる。こちらはマスの中のリンクを (3=8)r4c9 のように書けるので、数字が途中で入れ替わる鎖に向く。どちらの書き方でも、等号が強リンク、ハイフンが弱リンクという対応は同じだ。記号の並びが違って見えても、等号とハイフンを順に拾えば同じ鎖として読める。末尾に「=> r1c6<>8」と書いてあれば、それが鎖から出る結論である。
| 書き方 | この記事の鎖 | 向いている鎖 |
|---|---|---|
| Nice Loop の記法 | 8 r3c4 =8= r3c9 -8- r4c9 =8= r4c5 -8- r9c5 =8= r8c6 | 1 つの数字だけを追う鎖 |
| Eureka の記法 | (8)r3c4=(8)r3c9-(8)r4c9=(8)r4c5-(8)r9c5=(8)r8c6 | マスの中のリンクを含む鎖 |
| 言葉で書く | r3c4 と r8c6 の少なくとも一方は 8 | 結論だけを人に伝える時 |
どちらの記法でも、結論は r1c6<>8 (r1c6 は 8 ではない) である。
鎖の種類はリンクの材料で決まる
X-Chain や XY-Chain といった鎖の名前は、どの材料でリンクを作るかの違いである。記法が読めれば、名前を覚えていなくても鎖の正しさは確かめられる。X-Chain は 1 つの数字だけで作る鎖で、この記事の例がそれに当たる。リンクはすべてマスとマスの間にある。XY-Chain は候補が 2 つのマスだけを並べる鎖で、マスの中が強リンク、マスとマスの間が弱リンクになる。この盤の r4c9 と r4c5 はどちらも候補が 3 と 8 の 2 つなので、(3=8)r4c9 のようにマスの中の強リンクが作れる。リモートペアは XY-Chain のうち、すべてのマスが同じ 2 つの候補を持つ物で、HoDoKu によれば何かを消すには 4 マス以上の長さが要る。AIC は、これらの材料を制限なく混ぜて交互に並べた鎖の総称である。HoDoKu は、どの鎖も根は AIC だと述べている。なお 4 マスの X-Chain は Turbot Fish と呼ばれることがあり、W-Wing や XY-Wing も短い鎖として読める。
| 名前 | 強リンクの材料 | 弱リンクの材料 | 消せる物 |
|---|---|---|---|
| X-Chain | 1 つの数字の候補が 2 マスだけの行 / 列 / ブロック | 同じ数字の候補どうし | 両端を両方見るマスのその数字 |
| XY-Chain | 候補が 2 つのマスの中 | 隣り合うマスの同じ数字 | 両端の同じ数字を、両端を見るマスから |
| リモートペア | 同じ 2 候補のマスの中 | 同じ 2 候補のマスの間 | 4 マス以上で、両端を見るマスの 2 候補 |
| AIC | 上の材料の組み合わせ | 上の材料の組み合わせ | 両端の数字と位置で決まる |
定義は HoDoKu の「Chains and Loops」による。
よくある誤りと見分け方
1 つ目は、弱リンクを強リンクとして使うことだ。この盤の 5 列目には r4c5 / r6c5 / r9c5 の 3 マスに 8 の候補がある。「r4c5 が 8 でないから r9c5 が 8」と進むのは誤りで、r6c5 が 8 の可能性が残っている。等号を書く前に、その行 / 列 / ブロックの候補が本当に 2 マスかを数え直すとよい。2 つ目は、等号を「等しい」と読むことだ。r3c4 =8= r3c9 は 2 マスがどちらも 8 だという意味ではなく、少なくとも一方が 8 だという意味である。3 つ目は、強と弱が交互になっていない鎖を読むことだ。弱リンクが 2 つ続くと、「違う」から「違う」へ進むことになり、何も言えなくなる。4 つ目は、両端の片方からしか見えないマスの候補を消すことだ。消せるのは両端の両方から見えるマスだけで、この例では r1c6 と r7c4 がそれに当たり、8 の候補を持つのは r1c6 だけである。5 つ目は、候補の書き込みが古いまま鎖を作ることだ。直前に確定した数字の影響を候補に反映していないと、実際には 3 マスある所を 2 マスと数えて、存在しない強リンクを作ってしまう。
記法の次に読みたいもの
記法が読めるようになったら、短い鎖の形をしている既存の手筋に戻ると理解がつながる。カラーリングは、1 つの数字の強リンクをたどって 2 色に塗り分ける方法で、X-Chain と同じ材料を使う。W-Wing は、候補が同じ 2 つのマス 2 個を 1 本の強リンクでつなぐ形で、短い AIC として読める。XY-Wing は、候補が 2 つのマス 3 個でできた XY-Chain と見ることができる。それぞれの記事の図を、この記事の等号とハイフンで書き直してみると、どこが強リンクでどこが弱リンクかがはっきりする。用語集では、チェーン / 強リンク / 弱リンクの項目に、この記事で使った言葉の定義がある。