数独の解法とグラフ
以前、http://www.geocities.jp/master_mishichan/という数独の解法をたくさん集めたサイトを見つけました。ここにある解法を、数独ソルバーに組み込んで、ジェネレータを走らせて無理ゲーを大量生産したりしました。
ここには、Simple Chain、Remote Pairs、X-cycle、XY-cycle、AICといったサイクル系解法がたくさんあります。X-CycleはSimple Chain、Remote Pairsの、AICはX-Cycle、XY-Cycleの上位互換になっているようです。
ところで、「強いリンクと弱いリンクが交互になっているようなサイクルを探せ」と言われても、探索するのも少し面倒です。AICになると、探索範囲が広すぎてかなり時間がかかりそうです。そこで、リンクとは何かを考えることによって、サイクルをグラフに還元して解く方法を考えました。
リンクとは何か
あるブロック、列などの中に、ある数字（Xとする）を候補に持つマスが2個あるとき、どちらかにXが入らないといけません。この2つのマスの間には「強いリンク」があります。すなわち「強いリンク」は、「リンクを構成する2マスのうちちょうど1方にXが入る」ことを意味します。
3個以上そのようなマスがあっても、2マス以上にXは入りません。それぞれの間に「弱いリンク」があります。「弱いリンク」は、「リンクを構成する2マスのうち高々1方にしかXは入らない」ことを意味します。
サイクルとグラフ
数独において、あるマスに数字Xは「入るか入らないか」のどちらかです。そこで、マスと数字Xに対して、「入る」「入らない」の頂点を持つグラフを考えてみます。
AとBの間に強いリンクがあるとき、「Aに入る→Bに入らない」「Aに入らない→Bに入る」「Bに入る→Aに入らない」「Bに入らない→Aに入る」が成り立っています。
弱いリンクのときでも、「Aに入る→Bに入らない」「Bに入る→Aに入らない」が成り立っています。
三段論法からわかるように、「事象P→事象Qかつ事象Q→事象R」なら「事象P→事象R」なので、「AならばB」なら、Aを意味する頂点→Bを意味する頂点の辺を張って考えると、「AからBの経路が存在する」ならば「A→B」だとわかります。
このようにしてグラフができました。このグラフにおいて連結関係を見てみると、サイクル系解法とかなり密接に関わっていることがわかります。
まず不連続点のないX-cycleの場合については、グラフを構成すると、グラフ上でもサイクルができていることがわかります。グラフ上のサイクルを構成する点同士は、それぞれ同値なので、間にある弱いリンクも、実は強いリンクだったことがわかります。
不連続点のあるX-cycleの場合は、あるマスAが存在して、「AにXが入る→AにXが入らない」もしくはこの逆がグラフから読み取れます。この場合だと、AにXが入るか入らないかがすぐに決定されます（矛盾が起こるため）。
もちろん、この方法はX-cycleだけでなく、AICに対しても直接適用することが可能です。
