ナンバープレース,数独解法まとめ

超弩級テクニック

ここでは超上級テクニックで説明したCycle/Chainのより一般的な技術について二通りの説明をします。

1. Nice Loop

X-cycleやXY-chainをまとめたテクニックです。一般には難易度が極めて高い問題の解法に使用されています。

Nice Loopとは主に、強いリンク、弱いリンク、候補を二つだけ持つマス(Bivalueセル)をつなげて、輪になるように組み合わせたチェーンのことです。(強いリンク、弱いリンクについては超上級テクニックその2を参照してください。)

Nice Loopを構成する各リンクは以下の3つの規則に従っていなくてはなりません。

	強いリンクが別の強いリンクにつながる時は、両方のリンクのラベルは異なっていること。左図のように灰色のマスにxが、黄色のマスにyが、水色のマスにzがはいらないとき、この4つのマスはNice Loopの一部を構成することができます。
	弱いリンクが別の弱いリンクにつながる時は、両方のリンクのラベルは異なっていること。なおかつ、二つのリンクがつながっているマスは候補を二つだけもつBivalueセルでなくてはならない。(強いリンクは弱いリンクとしても扱えるので、このパターンは強→強、強→弱、弱→強、弱→弱のすべてのケースに適用できる) 左図の様にr1c4とr3c6がBivalueセルの時、この4つのマスはNice Loopの一部を構成する事ができます。
	強いリンクが別の弱いリンクにつながる時(またはその逆)は、両方のラベルは同一で、符号が逆になっていなくてはならない。(このパターンは強→強、強→弱、弱→強のケースに適用できる) 左図の様に灰色のマスにxが入らないとき、この4つのマスはNice Loopの一部を構成する事ができます。(注: box8のリンクは強いリンクだが、このケースでは弱いリンクとして扱っている)
上記3つのルールに従って組み立てられたチェーンを順にたどって行くとします。スタートするマスが弱いリンクとつながっているとき、スタートするマスにそのリンクのラベル数字が入ると仮定すると、そこから先の全ての強いリンクの下流側にそのリンクのラベル数字が、また弱いリンクの上流側にそのリンクのラベル数字が入る事になります。 (上記の2番目の例ではr1c1にxが、3番目の例ではr2c8にxがはいると仮定してチェックしてみてください) またスタートするマスが、強いリンクとつながっている時は、反対にそのマスにはリンクのラベルが入らないと仮定します。すると上記と同じように、チェーンのポイントポイントのマスが決まります。(全てのマスが決まるわけではない) 単なるチェーンでは、チェーンを構成するマスに上の様な関係があることしか言えません。ところが、このチェーンが輪を描いて最初のマスにつながりループを構成している場合には話が違ってきます。 Nice Loopでは上記3つのルールが全てのポイントで守られているループを連続ループと呼びます。また、1ヶ所だけルールを逸脱しているループを不連続ループと呼びます。連続ループの場合は次の２つのことがいえます。
	二つの強いリンクの間にあるマスにはどちらかのリンクのラベル数字しか入れることができない。左図で、灰色のマスにはxを水色のマスにはyをいれることができず、黄色のマスが図示したようなBivalueセルの場合、ピンクのマスにはxかyしか入れる事ができず、bが入る可能性はなくなります。
	弱いリンクを含むユニットにはリンクの両端のマス以外にラベル数字を入れることができない。上と同じケースで考えると、左図の場合、緑のマスにリンクのラベル数字を入れる事はできません。例えばbox5では黄色のマス以外にはwを入れることができません。
連続ループでは先に述べたやり方で左周りにも右回りにも完全に矛盾なくループを一巡することが可能です。(どのマスからでもスタートできる)さらにこのループが取りえる値はこの時にとる2通りのパターンしかありえません。強いリンクの間にあるマスは右回り左回りのどちらでも必ず、強いリンクの下流側に位置します。従って「二つの強いリンクの間にあるマスにはどちらかのリンクのラベル数字しか入れることができない」ということがわかります。また弱いリンクの両端のどちらかのマスには必ずラベル数字が入るため(右回りにしろ左回りにしろ、どちらかのマスが上流に位置する)、「弱いリンクを含むユニットにはリンクの両端のマス以外にラベル数字を入れることができない」ということがわかります。不連続ループの場合は、次の3つのケースで候補の削除または決定が可能です。
	同じラベルの強いリンクがつながっている場合: その二つのリンクがつながっているマスにラベル数字が入ります。左図の場合、ピンクのマスにはxが入ります。ピンクのマスにxが入らないとして、ループをたどると、ループを構成する全ての強いリンクの下流のマスにリンクのラベル数字が入ります。するとループを一周して戻った時、ピンクのマスにはxが入ることになりますが、これは最初の仮定と矛盾します。従って最初の仮定は誤りで、ピンクのマスにはxが入る事がわかります。
	同じラベルの弱いリンクがつながっている場合: その二つのリンクがつながっているマスからラベル数字の候補を取り除けます。左図の場合、ピンクのマスの候補からxを取り除くことができます。ピンクのマスにxが入るとしてループをたどると、ループを構成する全ての弱いリンクの上流のマスにリンクのラベル数字が入ることになりｍす。従って上の場合と同じ様に、矛盾が生じるからです。
	異なるラベルの強いリンクと弱いリンクがつながっている場合: その二つのリンクがつながっているマスから弱いラベル数字の候補を取り除けます。左図の場合、ピンクのマスの候補からyを取り除く事ができます。ピンクのマスにyが入るとして、弱いリンクの方向にチェーンをたどると、最後の強いリンクの下流のマスにxが入る事になり矛盾が生じるからです。
Nice Loopはその他のテクニックと組み合わせる事で、大幅に拡張することが可能です。ただ実際には色鉛筆とトレーシングペーパーや、お絵書き機能をもつサポートソフトがないと使いこなすのは難しいと思います。 Nice Loopを見つけ出す効率的な方法にBB Plotというやり方があります。

2. Alternate Inference Chain (AIC)

Chainに関する最も包括的でかつ単純な手法です。(はっきり言ってしまえば、ここで紹介する単純な考え方を身に付ければれば、その他X-cycle, Simple Chainなどのテクニックは不要です)ただし適用範囲があまりにも広すぎるため、場合によってはトライアンドエラーと変わらないんじゃない?ということになるかもしれません。Simple Chainなどと比べると連鎖の探索範囲が広く、慣れないとどうChainを組み立てて行けばいいのか、途方にくれてしまいます。(=ミシチャンの場合)

さて、この技術の説明に入る前に今まで何度も説明してきた考え方をガラッと替える必要があります。

これまで何度も連鎖について説明して来ましたが、その連鎖というのはある数字候補を介して結びつけられるマスとマスのつながりから成り立っていました。AICではこの考えを捨てます。AICにおける連鎖(すなわち複数の連続したリンク)のノードはマスではなく、数字候補になります。

	図で説明します。ある列にxが入るマスが二つしか無いとき、AICではこの数字候補xとxの間に強いリンクがあると考えます。ここまでだと別に今までのやり方と変わらないんじゃない?と思われるかもしれません。
	AICの特徴が一番はっきり現れるのはマスにその考え方を適用した場合です。あるマスにxかyのどちらかが入る場合、AICではそのxとyの間にも強いリンクがあると考えます。xyzの3候補を持つマスでは例えば、xとzの間に弱いリンクがあると考えます。
	AICとはこの様な考え方から見つかるリンクの連鎖のうち、強いリンクから始まり任意の強弱交互のリンクを介したあと、強いリンクで終わる一連の連鎖を指します。AICでは始まりの候補(ノード)と終わりのノードのどちらかは必ず真です。(理屈はX-cycle (連続ループ)と同じです。一番左の弱いリンクがあるか無いかの違いだけで、x/0を真/偽に置き換えてみてください。)したがって、例えば先頭ノードと終端ノードが同じ数字だった場合、両方のノードと共通のピアにあるマスにはその数字を入れることはできません。
	先頭ノードと終端ノードが弱いリンクで結びついているとき、AICはループとなります。この場合、AICを構成する全ての弱いリンクの端ノードのどちらかは必ず真となります。(上記同様理屈はX-cycle (連続ループ)と同じです。) XY-chainを考えてみます。XY-chainは弱いリンクから構成されると説明しましたが、AICの考え方でみると実際は強(マスの中)弱(マスとマス）の繰り返しだったことがわかります。 AICの考え方は基本的に連鎖系のテクニックなら全てに対応可能です。個人的な感想ですが、チェーンの探索範囲が広がりすぎてうまく使えたことがありません。論理の単純さを考えると人間よりもコンピュータに向いたテクニックかもしれません。

	強いリンクが別の強いリンクにつながる時は、両方のリンクのラベルは異なっていること。左図のように灰色のマスにxが、黄色のマスにyが、水色のマスにzがはいらないとき、この4つのマスはNice Loopの一部を構成することができます。
	弱いリンクが別の弱いリンクにつながる時は、両方のリンクのラベルは異なっていること。なおかつ、二つのリンクがつながっているマスは候補を二つだけもつBivalueセルでなくてはならない。(強いリンクは弱いリンクとしても扱えるので、このパターンは強→強、強→弱、弱→強、弱→弱のすべてのケースに適用できる) 左図の様にr1c4とr3c6がBivalueセルの時、この4つのマスはNice Loopの一部を構成する事ができます。
	強いリンクが別の弱いリンクにつながる時(またはその逆)は、両方のラベルは同一で、符号が逆になっていなくてはならない。(このパターンは強→強、強→弱、弱→強のケースに適用できる) 左図の様に灰色のマスにxが入らないとき、この4つのマスはNice Loopの一部を構成する事ができます。(注: box8のリンクは強いリンクだが、このケースでは弱いリンクとして扱っている)
上記3つのルールに従って組み立てられたチェーンを順にたどって行くとします。スタートするマスが弱いリンクとつながっているとき、スタートするマスにそのリンクのラベル数字が入ると仮定すると、そこから先の全ての強いリンクの下流側にそのリンクのラベル数字が、また弱いリンクの上流側にそのリンクのラベル数字が入る事になります。 (上記の2番目の例ではr1c1にxが、3番目の例ではr2c8にxがはいると仮定してチェックしてみてください) またスタートするマスが、強いリンクとつながっている時は、反対にそのマスにはリンクのラベルが入らないと仮定します。すると上記と同じように、チェーンのポイントポイントのマスが決まります。(全てのマスが決まるわけではない) 単なるチェーンでは、チェーンを構成するマスに上の様な関係があることしか言えません。ところが、このチェーンが輪を描いて最初のマスにつながりループを構成している場合には話が違ってきます。 Nice Loopでは上記3つのルールが全てのポイントで守られているループを連続ループと呼びます。また、1ヶ所だけルールを逸脱しているループを不連続ループと呼びます。連続ループの場合は次の２つのことがいえます。
	二つの強いリンクの間にあるマスにはどちらかのリンクのラベル数字しか入れることができない。左図で、灰色のマスにはxを水色のマスにはyをいれることができず、黄色のマスが図示したようなBivalueセルの場合、ピンクのマスにはxかyしか入れる事ができず、bが入る可能性はなくなります。
	弱いリンクを含むユニットにはリンクの両端のマス以外にラベル数字を入れることができない。上と同じケースで考えると、左図の場合、緑のマスにリンクのラベル数字を入れる事はできません。例えばbox5では黄色のマス以外にはwを入れることができません。
連続ループでは先に述べたやり方で左周りにも右回りにも完全に矛盾なくループを一巡することが可能です。(どのマスからでもスタートできる)さらにこのループが取りえる値はこの時にとる2通りのパターンしかありえません。強いリンクの間にあるマスは右回り左回りのどちらでも必ず、強いリンクの下流側に位置します。従って「二つの強いリンクの間にあるマスにはどちらかのリンクのラベル数字しか入れることができない」ということがわかります。また弱いリンクの両端のどちらかのマスには必ずラベル数字が入るため(右回りにしろ左回りにしろ、どちらかのマスが上流に位置する)、「弱いリンクを含むユニットにはリンクの両端のマス以外にラベル数字を入れることができない」ということがわかります。不連続ループの場合は、次の3つのケースで候補の削除または決定が可能です。
	同じラベルの強いリンクがつながっている場合: その二つのリンクがつながっているマスにラベル数字が入ります。左図の場合、ピンクのマスにはxが入ります。ピンクのマスにxが入らないとして、ループをたどると、ループを構成する全ての強いリンクの下流のマスにリンクのラベル数字が入ります。するとループを一周して戻った時、ピンクのマスにはxが入ることになりますが、これは最初の仮定と矛盾します。従って最初の仮定は誤りで、ピンクのマスにはxが入る事がわかります。
	同じラベルの弱いリンクがつながっている場合: その二つのリンクがつながっているマスからラベル数字の候補を取り除けます。左図の場合、ピンクのマスの候補からxを取り除くことができます。ピンクのマスにxが入るとしてループをたどると、ループを構成する全ての弱いリンクの上流のマスにリンクのラベル数字が入ることになりｍす。従って上の場合と同じ様に、矛盾が生じるからです。
	異なるラベルの強いリンクと弱いリンクがつながっている場合: その二つのリンクがつながっているマスから弱いラベル数字の候補を取り除けます。左図の場合、ピンクのマスの候補からyを取り除く事ができます。ピンクのマスにyが入るとして、弱いリンクの方向にチェーンをたどると、最後の強いリンクの下流のマスにxが入る事になり矛盾が生じるからです。
Nice Loopはその他のテクニックと組み合わせる事で、大幅に拡張することが可能です。ただ実際には色鉛筆とトレーシングペーパーや、お絵書き機能をもつサポートソフトがないと使いこなすのは難しいと思います。 Nice Loopを見つけ出す効率的な方法にBB Plotというやり方があります。