← StudyX Devlog

数独のチェーンとは:強いリンクと弱いリンクの考え方

Hiroki ObaraHiroki Obara · DeveloperSudoku365使い方
数独のチェーンとは:強いリンクと弱いリンクの考え方

ナンプレ(数独)の上級の手筋を英語の解説で読むと、「strong link(強いリンク)」「weak link(弱いリンク)」「chain(チェーン)」という言葉がよく出てきます。どれも、候補どうしのつながりを表す言葉です。

これまでの記事では、Xウィング、ソードフィッシュ、XYウィング、ユニークレクタングル を、それぞれの形として説明してきました。この記事では、その下にあるリンクとチェーンの考え方を、例の盤面1つで順にたどります。

言葉はこれまでの記事と同じです。横の並びを「行」、縦の並びを「列」、3×3の太枠を「ブロック」、あるマスに入る可能性のある数字を「候補」と呼びます。マスの場所は「4行目8列目」のように書きます。

強いリンクと弱いリンク

英語の手筋解説 HoDoKu の Chains and Loops のページは、2つのリンクを次のように定義しています。

  • 弱いリンクでつながった2つの候補は、両方が正しいことはない。
  • 強いリンクでつながった2つの候補は、両方がまちがいであることはない。

同じページは、これを「弱いリンク: aが正しければ、bはまちがい」「強いリンク: aがまちがいなら、bが正しい」とも言いかえています。強いリンクは「どちらか片方は必ず入る」、弱いリンクは「両方は入らない」ということです。

1つの数字で作るリンク

1本の行、列、ブロックの中で、ある数字の候補が2つのマスにしかないとします。その数字はどこかに入るので、片方がまちがいなら、もう片方が正しくなります。これが強いリンクです。HoDoKu のページも、強いリンクには、同じ数字の候補が1つの行・列・ブロックの中にちょうど2つあることが必要だとしています。

同じ行・列・ブロックにある同じ数字の候補は、数がいくつでも、2つ同時には入りません。これは数独のルールそのものなので、どの2つを選んでも弱いリンクになります。

英語の解説サイト SudokuWiki の Weak and Strong Links のページには、列の中に9の候補が3つ以上ある例があります。そこでは、候補が2つより多いので強いリンクは作れない、と書かれています。

1つのマスの中で作るリンク

リンクは、1つのマスの中の違う数字どうしでも作れます。候補が2つだけのマス、たとえば6と8だけのマスなら、6でなければ8が入ります。これも強いリンクです。HoDoKu のページは、候補が2つのマスの中には、その2つの候補のあいだに強いリンクがある、と書いています。

1つのマスには数字が1つしか入らないので、同じマスの違う候補どうしは、いつも弱いリンクです。候補が3つ以上あるマスでは、強いリンクはできません。

まとめると、強いリンクができるのは次の2つの場合です。

  • 1本の行、列、ブロックの中で、ある数字の候補がちょうど2つのとき(同じ数字どうし)
  • 1つのマスの候補がちょうど2つのとき(同じマスの違う数字どうし)

SudokuWiki では、前者を bi-location、後者を bi-value と呼んでいます。

強いリンクは弱いリンクとしても使える

候補が2つしかない行の2マスは、「片方は必ず入る」と同時に「両方は入らない」も満たしています。HoDoKu のページは、強いリンクでつながった2つの候補はいつも弱いリンクでもつながっていて、強いリンクを弱いリンクとして使えるが、その逆はできない、と書いています。

チェーンのつなぎ方

HoDoKu のページは、チェーンを「前提から結果へ向かう、推論の連なり」と説明しています。前提はたとえば「このマスのこの候補は入らない」です。

リンクをつないでチェーンにするときは、強いリンクと弱いリンクを交互に使います。HoDoKu のページは、リンクの種類を交互にしなければならない、と書いています。理由は定義から分かります。強いリンクは「まちがいなら、次が正しい」、弱いリンクは「正しいなら、次がまちがい」なので、交互につなぐと推論が途切れずに進みます。

1つの数字だけを使うチェーンは、X-Chain と呼ばれます。HoDoKu のページによると、X-Chain は強いリンクで始まり、強いリンクで終わります。そして、チェーンの両端のマスの両方と同じ行・列・ブロックにあるマスから、その数字を消せます。

例の盤面

次の盤面は、ある問題を途中まで解いたところです。この問題の答えは1つです。「・」は空いているマスです。

       1 2 3   4 5 6   7 8 9
1行目  5 6 3 | 7 1 ・ | ・ ・ 2
2行目  7 9 1 | 6 ・ ・ | ・ 5 ・
3行目  4 8 2 | 3 5 9 | 7 1 6

4行目  3 7 ・ | 2 4 1 | 8 ・ ・
5行目  ・ ・ ・ | 9 6 7 | ・ 3 ・
6行目  ・ 1 ・ | 5 ・ ・ | ・ 4 7

7行目  ・ 5 ・ | ・ ・ ・ | ・ 7 ・
8行目  ・ ・ 7 | ・ 9 ・ | ・ ・ ・
9行目  9 3 ・ | 1 7 5 | ・ 2 ・

空いているマスは37です。この盤面では、候補が1つだけのマスもなく、行・列・ブロックの中で入る場所が1つだけの数字もありません。

6のリンクを探す

数字の6に注目します。6が入れるマスは、次の○です。

       1 2 3   4 5 6   7 8 9
1行目  5 6 3 | 7 1 ・ | ・ ・ 2
2行目  7 9 1 | 6 ・ ・ | ・ 5 ・
3行目  4 8 2 | 3 5 9 | 7 1 6

4行目  3 7 ○ | 2 4 1 | 8 ○ ・
5行目  ・ ・ ・ | 9 6 7 | ・ 3 ・
6行目  ○ 1 ○ | 5 ・ ・ | ○ 4 7

7行目  ○ 5 ○ | ・ ・ ○ | ○ 7 ・
8行目  ○ ・ 7 | ・ 9 ○ | ○ ○ ・
9行目  9 3 ○ | 1 7 5 | ○ 2 ・

4行目の空いているマスは、3列目、8列目、9列目の3つです。9列目には3行目に6があるので、6が入れるのは3列目と8列目の2マスだけです。4行目3列目と4行目8列目は強いリンクでつながっています。

9行目の空いているマスも、3列目、7列目、9列目の3つです。やはり9列目は外れるので、6が入れるのは3列目と7列目の2マスです。9行目3列目と9行目7列目も強いリンクです。

3列目では、6が入れるマスは4行目、6行目、7行目、9行目の4つです。候補が4つあるので、4行目3列目と9行目3列目は強いリンクではありません。同じ列なので、弱いリンクです。

4つの候補のチェーン

この3本のリンクを、強い、弱い、強いの順につなぎます。

  • 4行目8列目が6でないなら、4行目の強いリンクで、4行目3列目が6です。
  • 4行目3列目が6なら、3列目の弱いリンクで、9行目3列目は6ではありません。
  • 9行目3列目が6でないなら、9行目の強いリンクで、9行目7列目が6です。

つまり、4行目8列目と9行目7列目の、少なくともどちらか一方は6です。チェーンは強いリンクで始まり、強いリンクで終わっているので、HoDoKu の X-Chain の形になっています。

       1 2 3   4 5 6   7 8 9
1行目  5 6 3 | 7 1 ・ | ・ ・ 2
2行目  7 9 1 | 6 ・ ・ | ・ 5 ・
3行目  4 8 2 | 3 5 9 | 7 1 6

4行目  3 7 ◎ | 2 4 1 | 8 ◎ ・
5行目  ・ ・ ・ | 9 6 7 | ・ 3 ・
6行目  ・ 1 ・ | 5 ・ ・ | × 4 7

7行目  ・ 5 ・ | ・ ・ ・ | ・ 7 ・
8行目  ・ ・ 7 | ・ 9 ・ | ・ × ・
9行目  9 3 ◎ | 1 7 5 | ◎ 2 ・

両端の4行目8列目と9行目7列目の、両方と同じ行・列・ブロックにある6の候補は、×の2つです。

  • 6行目7列目は、4行目8列目と同じ右の真ん中のブロックにあり、9行目7列目と同じ7列目にあります。
  • 8行目8列目は、4行目8列目と同じ8列目にあり、9行目7列目と同じ右下のブロックにあります。

どちらの端が6でも、この2マスは6になれません。だから6行目7列目と8行目8列目から6を消せます。

マスの中のリンクで決まる

8行目8列目の候補は、6と8の2つでした。8行目には7と9が、8列目には1、2、3、4、5、7が、右下のブロックには2と7があるからです。このマスの中で、6と8は強いリンクでつながっています。6が消えたので、8行目8列目は8に決まります。

この盤面は、そのあとは候補が1つだけのマスや、入る場所が1つだけの数字を順に埋めていくと、最後まで解けます。

スカイスクレイパーとXウィング

いま使った形には名前があります。HoDoKu の Single Digit Patterns のページは、スカイスクレイパー(Skyscraper)を次のように説明しています。1つの数字に注目し、その数字の候補が2つだけの行を2本見つける。そのうち2つの候補が同じ列にあれば、残りの2つのどちらかは正しい。その両方から見えるマスの候補は消せる。この盤面の4行目と9行目は、3列目で候補がそろい、残りが8列目と7列目に分かれています。Chains and Loops のページには、4つの候補の X-Chain は Turbot Fish と呼ばれることがあると書かれています。Single Digit Patterns のページでは、スカイスクレイパーは Turbot Fish の特別な形とされています。

Xウィング も、同じようにリンクで言いかえられます。Xウィングの記事の盤面では、3行目と6行目で、2が入れるマスがどちらも2列目と9列目の2つだけでした。3行目2列目と3行目9列目、6行目2列目と6行目9列目が、それぞれ強いリンクです。

  • 3行目2列目が2でないなら、3行目9列目が2です。
  • 3行目9列目が2なら、同じ9列目の6行目9列目は2ではありません。
  • 6行目9列目が2でないなら、6行目2列目が2です。

両端の3行目2列目と6行目2列目は、どちらも2列目にあります。どちらかが2なので、2列目のほかのマスから2を消せます。同じチェーンを逆向きにたどると、9列目のほかのマスからも消せます。スカイスクレイパーとの違いは、2本の行の残りの2マスも同じ列にそろっていることです。

仮定とチェーン

数独で仮定(当てずっぽう)を使ってもいいか の記事では、数字を1つ仮に置いて、矛盾が出るかを確かめる進め方を書きました。

上の例のチェーンも「4行目8列目が6でないなら」という「もし」から始まります。ただ、どちらかの答えを選んで先へ進めることはしていません。4行目8列目が6の場合も、6でない場合も、6行目7列目と8行目8列目には6が入らない、という結論になります。どの一歩も、強いリンクか弱いリンクのどちらかで、行・列・ブロックのルールから出ています。

リンクは、メモが正しいことが前提です。強いリンクは「候補が2つしかない」ことから作るので、どこかで候補を1つ書き落としていると、強いリンクでないものを強いリンクと見てしまいます。メモの書き方は ナンプレのメモ(候補数字)の書き方 に書きました。

Sudoku365 について

Sudoku365 は、iPhone、iPad、Android で遊べる数独のアプリです。盤は標準の 9×9 です。「かんたん」「ふつう」「むずかしい」「エキスパート」の四つの難易度に 300 問ずつ、計 1200 問が入っています。毎日一問のデイリーチャレンジと連続記録があり、Bluetooth で2人で対戦や協力をすることもできます。

ゲーム画面の「メモ」をオンにすると、マスに候補を書けます。設定の「メモから数字を消す」(初期はオン)にしておくと、正しい数字を置いたときに、関係するマスの同じメモが自動で消えます。マスを選ぶと、同じ行・列・ブロックと、同じ数字のマスがハイライトされます。

アプリは無料で、広告が入ります。「広告を削除」の買い切り(1,500円)で広告を消せます。ひとりで毎日続けるための使い方は Sudoku365 活用のヒント に、最初の一問の始め方は Sudoku365 の始め方 に書きました。

App Store でダウンロード Google Play で手に入れよう

Sudoku365毎日ナンプレ、2人でも