マニア向け手筋を紹介。気が向いたら更新します。今回のテーマはチェインです。
基本的な考え方
チェインは、数字が入るかどうかの情報を連鎖させて、候補数字を消していく手筋の総称です。
考え方の基本となるのは「ある数字があるマスに入るかどうか」(たとえば、1がr3c7に入るか、など) の命題で、パズルを解くことは各命題について真か偽を定めていくことと等価です。真とわかればその数字がそのマスに入るし、偽とわかればそのマスの候補数字が消せたことになります。
2つの命題の関係性について、特別なものに名前をつけておきます。
そのひとつが弱チェインです。これは「2つの命題の少なくとも一方が偽」＝「2つの命題が両方真にはならない」ことをいいます。
もうひとつが強チェインです。これは「2つの命題の少なくとも一方が真」＝「2つの命題が両方偽にはならない」ことをいいます。
図は真偽のパターンを表にしたものです。Tは真 (True)、Fは偽 (False) を表します。
数独において、「1つの数字について同じ行・列・箱の2マスに入るかどうか」や「1つのマスについて2つの別の数字が入るかどうか」、などが弱チェインを成します。さらにそれらが二択になっているとき、強チェインを成します。
(強チェインでは主に二択のケースを考えるので、上の表のAがTかつBがTは×になることが多い、この場合弱チェインにもなっている。)
図はチェインの例を表しています。左上の例では「r1c2の1」と「r1c8の1」が弱チェインを成しており、一番右の例では1つのマスについて候補の1と候補の3が強チェインを成しています。なお、図では弱チェインは破線で、強チェインは実線で表すこととします。
チェインの手筋とは、命題の弱チェインと強チェインのつながりを見て真偽を定めることを指します。特に大事なのは、弱チェインと強チェインが交互に来るものです。
図の左の状況を考えます。頂点は命題を表すものとして、それらがチェインでつながっています。さらに上の頂点を始点に弱チェインと強チェインが交互にあるとします。
このとき、上の頂点の命題がTとすると、チェインをたどって各命題の真偽が決まります (真偽の組み合わせを思い出しましょう) 。すると、一周戻ってきたときFとなってしまい矛盾します。したがって上の頂点の命題はF、つまり偽となるのです。
大事なのは、この議論は強弱チェインが交互で長さが奇数なら全く同様に成立することです。始点につながるチェインが弱ならば、始点の命題は偽に、始点につながるチェインが強ならば、始点の命題は真になります (多くの場合前者となります)。
さて偶数長ならどうでしょうか。この場合はTとFの個数が同数となり、結果弱チェインが強チェインに昇格します。すると、もともと弱チェインで三択以上だった部分が二択に絞られることとなり、他の候補が消去できるのです。最たる例がX-wing (井桁理論) で、これは長さ4のチェインといえます。
いずれにせよチェインを追うときは、交互にある強弱チェインのループを探すことになります。
実際の出現パターン
ではチェインに探すにはどうすればいいでしょうか。実際に数独の盤面でチェインを追うと、強弱のチェインが大量にあって困ることとなります。そこで、あらかじめ短いチェインの出現パターンを見ておくとよいでしょう。このとき出てくるのが、「あんまり～」で紹介したSkyscraper、XY-Wing、W-Wingなのです。
図のSkyscraperは長さ5のチェインです。「土台が同じ行」と言っていたのはこれらが弱チェインであることを指していました。また天井両方に利くマスとは天井の2マスと弱チェインでつなげられるということで、そのマスを含めて強弱交互のループが作れました。そのマスで候補が消せるのです。
1つの数字に注目したチェインをX-chainとよびます。最短だとSkyscraperのような長さ5のチェインになりますが、他にもTurbo Fishや2-String Kiteといったパターンがあります。あとは対角線ナンプレなどで情報が追加されると長さ3のX-chainが出てくることもあります (それはもはやチェインと呼べるか怪しいですが)。
図のXY-Wingは1マスの二択を連鎖させたものです。チェインの線を引くと議論がわかりやすいかと思います。弱チェインを作るには同じ候補数字が同じ行列箱に存在する必要があることに注意しましょう。
二択のマスを増やしても同じ議論ができ、そのパターンをXY-chainとよびます。各マスに候補数字を書くとXY-chainが見つけやすくなります。
また同じ二択ばかり考えることもでき (たとえば1と2の二択ばかりを考えるとか)、その場合は特にRemote Pairとよびます。Remote Pairくらいならニコリでも出せるかもしれない？
位置の二択とマスの二択のハイブリッドがW-Wingでしたが、これもチェインの一種です。一般にチェインを考えるときはさらに複雑なパターンが出てくることになります。ここでもやはり大事なのは強弱が交互ということです。(一般のケースはAlternate Inference Chain、略してAICなどとよぶようです。)
チェインの亜種
少し変わったパターンのチェインもあります。
まずは命題をまとめて考えるもの、たとえば「1がr1c2またはr1c3に入る」といったものです。分かりやすい例が、次のEmpty Rectangleです。
Empty Rectangleは1つの数字に注目する手筋で、図のような状況を考えます。このとき丸で囲ったようにまとめて命題を考えることでチェインが作れ、桃色マスを候補から外せます。
一般のチェインの途中でも命題をまとめて扱うことができます。(Grouped AICなどとよぶ。)
また関連して、ALS (Almost Locked Set) がチェインに現れることもあります。ALSとは「同じ行列箱のN個のマスにN個の候補数字がある」という状態であるいわゆる予約に比べると弱い状態で、N個のマスにN+1個の候補数字があることを指します。このとき、ALSに属する2つの候補数字について、入るマスをグループ化すれば強チェインが形成されます。1マスの二択の拡張みたいなもので (N=1だと1マスの二択)、強チェインを作る手段として強力といえます。ALSの詳しい説明はここでは書ききれないので、また今度にしますか。
チェインの亜種のもう一つは、チェインの途中に余計な数字 (いわゆるFin) は混入するパターン。分かりやすい例が、次のXYZ-Wingです。
図の状況では、r1c5の1がなければXY-wingが成立してr1c6の1が消えます。一方r1c5が1でもr1c6は1にならないので、いずれにせよr1c6に1は入りません (同様にr1c4にも入らない)。
一般にどうよぶかは分からない (出てくるかすらわからない) ですが、少なくともこのXYZ-wingはたまーに出てきます。もっと一般に余計な部分がFish (井桁理論の一般系、いずれ書くかも) になるときもあります。もっとも、Fishの方が大きい機構なのでチェインのほうがおまけな気もしますが (Kraken Fishなどとよばれるようです)。
いずれにせよ、グループ化やらALSやらFinやらFishやらを考え出すと出現パターンがありえないほど増えてしまい、チェインの発見は人間の力では非常に困難になるでしょう。
とりあえず普段使いできそうなものは、Empty RectangleとXYZ-wingあたりでしょうか。
おわりに
チェインとしてよく出てくるパターンはだいたい挙げたので、この辺にしておきましょう。
長ーいチェインや複雑なチェインを追うのは、人間には厳しいと思います。Hodokuの難易度Extremeの答えを眺めるとヤバめのチェインが出てきて楽しいですが、実戦では上で見たような特殊な名前のついているものを使うのが限界でしょう。ぎりぎりXY-chainで短めのくらいですかね。
なお、チェインの考え方は他のパズルでも利用できます。マインスイーパーなんかがそうですね。その場合は「このマスに地雷が入る」という命題でチェインしていくことになります。数独で1つの数字の位置を探る感じに似てるかも。しかしGrouped chainになることは必須で、それはそれで大変です。興味のある人はChocolate Sweeperなどをしてみるとよいでしょう。
さて今後はどうしますかね。FishとALSは書いておきたいなぁ。ちなみにこの記事は、自分の思考の整理という側面が強いです (つまり自己満！) なので別に公開しなくてもいいんですが、反響があればまた公開するかも。
