数独の解法とグラフ、つづき

Puzzle

Grouped AIC への拡張

AICは、「複数マスを1つだと思う」技法によって大幅に拡張されます。そうすると普通にサイクルを見つけるのでは実装が大変なことになりそうですが、グラフを用いるとただ頂点と辺を追加するだけで統一的に解けます。
Grouped AICにおいて、頂点は「対応するどれかの条件が真になる」と、その反対の「対応するどの条件も偽になる」を表します。辺を張ることができる条件は、2つのグループのどの構成要素も同じグループに属しかつ、同じ数字の条件であるなら、弱いリンクを張ることができ、さらにそのグループにその数字のマスが他に存在しないなら、強いリンクを張ることができます。ところで、Grouped AICといえども「同じマスの複数の候補」をグループ化する行為には何の意味もないようです。

グループ数の爆発を抑える

このまま実装すると、「どのマスをグループとしてみなすか」が大きな問題となります。とりあえず、「他の2箇所につなげたい」ということから、「2つのグループの共通点」に収まっているマス組だけを考えればいいと思われます。そして、共通点からマスを省いたものには「あまり」意味が無いこともわかります。すると、実際には埋まっているマスなどの関係もあり、必要なグループ数はわりと少なくなることがわかります。

しかし、マスを省いたものに「あまり」意味がないというのは、少しは意味があるということであり、例として「1つのブロックの中に、2つの3マスグループが直交していて、他にその数字が入るマスがない」という状況が挙げられます。このときは、そのままだと2つのグループは共通するマスを持つため、リンクを張ることができません。

その場合でも、「どちらかに入る」という条件は存在します。ならば、「AにXが入らない→BにXが入る」「BにXが入らない→AにXが入る」という条件で辺を張ってしまいまって構いません。すると、ほとんどの場合は普通にブロックを調節した場合と同じ働きをします。このリンクを「半端なリンク」と呼ぶことにします。「半端なリンク」は、サイクルにおいて強いリンクと同じ働きをしますが、強いリンクと異なり弱いリンクに代用ができません。しかし、この場合それはほとんど問題になりません。弱いリンクに代用するぐらいなら、最初から1マスだけのものと弱いリンクでつないでれば良いのです。

「半端なリンク」をもとに、ALSへの拡張

ALS（Almost Locked Sets）とは、「n+1個の数字候補を持つn個のマスの組」です。

あるALSをPと置き、Pに含まれる数字候補2つをx,yとおくと、「Pにxが含まれる」と「Pにyが含まれる」は少なくとも一方が成り立つことがわかります。さもなくば、「n-1個の数字候補を持つn個のマスの組」になってしまいます。

さて、ALSから導ける上の条件があれば、AICと全く統一的にALSを扱うことができます。

Grouped AICにおいて、ALSの構成マスからなるグループもグループとして作ってやります。このグループは、元のGrouped AICにおけるグループとほとんど同様に扱えます。ただ1つ違うのは、「同じALSに属していて、数字候補だけが違うグループ」の間には、半端なリンクを張れるということです。このようにすると、Grouped AICの中に完全にALSを組み込むことができます。あとは普通にグラフを解けばおしまいです。

この「Grouped AIC + ALS」の考えで、例のページにあるXYZ-Wing、WXYZ-Wingや、Death Blossomを統一的に扱うことができます。

ALSのもう一つの側面

今の場合、「n+1個の候補を持つnマス」をALSだと思いました。これは「n国同盟」をalmostにしたものです。n国同盟とFishはかなり密接に関連していて、その類推で「行から構成されるALS」なども考えられそうです。

実際にそのようなALSを構成することができます。ある数字xに対して、n個の行を選んだ時、xの入りうるマスがn+1個の列に収まったとき、このn個の行はALSです。
よってこのとき、候補になるn+1個の列をそれぞれグループと見たとき、各グループの間に半端なリンクが張れます。もちろんこの議論は行と列を入れ替えても同様に成り立ちます。当然、これは普通のALSと同様、Grouped AICの拡張として書くことができます。

この「Fishy ALS」を用いると、Finned FishやSashimi Fishなどを統一的に説明することができます。

AIC + Grouping + Cellular ALS + Fishy ALS の威力

説明上、―を強いリンク、〜を半端なリンク、…を弱いリンクとします。

これらを組み合わせると、ものすごいパターンを考えることができます。

上のパターンで、r1,r3にはc2,c5,c7以外にxを入れることができません。また、r5c5に入る候補はx,y、r8c5に入る候補はx,y,z、r8c8に入る候補はx,zだけとなっています。これだけの条件で、3箇所xを排除できるマスがあります。

まず、r1とr3の組がxについてALSになっています。すると、(r13c5)x〜(r13c7)xが得られます。
次に、r5c5とr8c5の2マスには、x,y,zしか現れないので、この2マスでALSになっています。すると、(r58c5)x〜(r8c5)zを得ます。
さらに、r8c8のマスでは、x,zしか現れないので、(r8c8)x―(r8c8)zとなります。
同じグループに属することから、(r13c5)x…(r58c5)x、(r8c5)z…(r8c8)zとなります。
以上より、
(r13c7)x〜(r13c5)x…(r58c5)x〜(r8c5)z…(r8c8)z―(r8c8)x
のチェーンを得ます。
両端(r13c7)、(r8c8)の両方を見ることができるマスにはxは入らないので、結果としてr2c8、r7c7、r9c7の3箇所からxを排除できることがわかります。