ナンバープレース,数独解法まとめここまでやる?級テクニック

ここまでやる？級テクニック

1. 背理法

ナンプレの解法で背理法というときはトライアンドエラーとか仮定した数字の試し置きの意味で使われることが一般的です。

通常は二つある候補数字の一方を選択してそれによる影響をチェックし、矛盾が発生した場合、選択しなかった方が正というものです。矛盾が生じなかった場合、どちらが正しいかは不明です。(選択した方が正しいとは言えない)

この手法はあまり好まれていません。理由の一つは数打てばあたる系であまりロジカルでないことがあげられると思います。(パズル的ではない)

それよりも最大の問題は選択した結果、場合によってはパズルが解けてしまうということにあると思われます。この場合、パズルの解き味もへったくれもなくなってしまいます。

これは数字を当てはめて試す系のテクニックに共通した欠点です。ほとんど全てのナンプレには秘孔みたいなツボがあって、ある段階でそのマスに入る数値が確定すると一気にパズル全体が解けてしまいます。秘孔とよべる弱点がないという問題も見つかっているそうですが、ごくごく例外です。まぐれで秘孔をついてしまった場合、普通はあまりうれしくないと思います。

背理法を使わないと解けないという問題を解くための手法を考えるのは挑戦しがいのある問題ですが、背理法を使って解く問題というのはあまり楽しいとは思えません。

2. Nishio

パズル作家の西尾さんの名前がつけられているテクニックです。理詰めではなく、トライアンドエラー手法の一つですが、やみくもにあたるのではなく、系統立てて探索する方法です。

いろんな説明があって、どれが正しいのかよくわからないので(英語も難しい), 一番理解が簡単だったSudoku Susserのマニュアルベースで説明します。

まず最初に探索を開始するマスとそのマスに入る仮の数字xを決定します。
そのマスにSのマークを書きます。次にそのマスにxがはいると仮定したことで他にxがはいることが決まるマスがあればそのマスに丸のマークをふります。すでにxがはいっているマスも丸マークをふります。またxが入るかどうかわからないマスは三角マークをふります。xがはいらないマスはそのままにします。
Sのマークのマスを丸マークに書き換えます。次に三角のマスのなかで、あるユニット(列、ボックス)に一つしかないマスを探します。その様な三角のマスがない場合、最初の選択がうまくなかったので1にもどって新たなスタートを別のマスからはじめます。
うまくユニット内で孤立している三角マスがみつかったら、そのマスをSに書き換えます。
Sマスと同じ列、ボックスにある三角のマスのマークを消して無印にします。
ここで、盤面をチェックします。丸も三角のマークもない列、ボックスがあったとしたら、そのユニットにはxがはいらないことになるので、矛盾が生じていることがわかります。
もしなんの矛盾も生じていないようなら3に戻って同じ作業を繰り返します。三角のマスがなくなったり、孤立した三角のマスが見つからなくなった時は最初の選択がこの手法にむいていなかったという事なので新たなスタートを別のマスからはじめます。

ちなみに、全く違うやり方が説明されている場合もあって、正しいのは何？という感じです。

肝心なのは、あるマスに仮の数字xを置いたとき、そのことが他の場所にxをいれてパズルを完成させる妨げになるかどうかをチェックすることにあるようです。普通の仮置きだと探索先がどんどん広がるのに対し、ただ一つの数字に対象をしぼることで、検討のスピードと正確性をあげることを狙った手法だと思います。

3 Forcing Chain/Net

Forcing ChainとはあるマスXに入る数字候補のどれを採用しても、あるマスYの値が同じ場合、Yのマスにはその数字がはいるという手法です。全く戦略を持たない場合は、どのマスからスタートするか、どのマスの値が変化しないかを探すのは正直かなりしんどい作業だと思います。個人的には背理法以上に使いたくないです。 Forcing Chainをロジカルにし戦略をたてて、連鎖をみつけていく手法が一連のChainやCycleといった技術ではないでしょうか。
	具体例です。あるパズルを左の例まで解いたとします。小さな文字は各マスに入る可能性のある数です。ここでr1c1とr4c2の数に注目してみます。
	r1c1に5が入った場合、左図の様にマスに入る数字が確定しr4c2=3となります。
	r1c1に6を入れた場合を考えると、左図の様になってやはりr4c2=3です。 r1c1が5でも6でも関係なしにr4c2=3となるので、このマスは3が確定します。

4 Pattern Overlay Method

調べた限りでは、最強の手法、背理法でしか解けないといわれている問題も解けることがあるというすごい技の様ですが、とにかく適用が大変です。

言葉で説明するのはミシチャンには不可能なので、具体例で説明してみます。

以下工事中 (もしかすると永遠に工事中かも. )

5. Template Method

これはコンピューターでしか使うことができない手法です。ナンプレである数字に注目した時、その数字の並べ方は全部で46,656通りあります。
(左の図の様に上の行から順に何通りずつ入る場所があるか考えると、
9*6*3*6*4*2*3*2*1 = 46656)

この46,656通りのパターンを全て揃えて置き、現時点で確定しているマス、入らない事がわかっているマスを使って、取りえるパターンを抜き出します。この取りえるパターンだけを調べ、全てのパターンで埋まっているマスがあれば、そのマスは確定します。また逆に全てのパターンで空白になっていれば、そのマスには入らないことがわかります。
さらに、他の数字でも同様の事を繰り返し、相互のパターンを比較して重なりあってしまうパターンを取り除いていけば、最終的に解を得る事ができます。

ものすごい力技の解法ですが、想像するほど計算量は多くない様です。(9x9の場合)例えば左の様にある数字が3ヶ所決まっていると、取りえるパターンは64通りしか残りません。(試しにやってみました)

6. Advanced Coloring

Simple Coloring (Simple Chain)やMulti Coloringではある一つの数字候補に注目して色分けを行いました。Advanced Coloring以上のテクニックではColoringの対象は複数の数字候補です。
左の問題を例にして試してみたいと思います。この問題はSudoku Susserに例題として載っているMenneske.noの＃1976940 Super Hardです。

(あまり良い例ではなかった。でも他のを試す気力はないので、、、)

基本的なテクニックを使うと左の状態まで持っていく事ができます。
(本来ならここで59のUnique Rectangleを使うのですが、、、)

まず数字候補の2に注目して色分けしてみます。

左の様に、aとb二つのグループにわけられます。
普通のColoringではこの時点でストップですが、Advanced Coloringではさらに色分けを進めます。

例えばr2c1に注目すると、このマスは2と3二つの候補をもち、2がaに色分けされています。このマスに2が入らない時、3が確定するので、この3をbで色分けし、今度は3に注目して色分けを進めます。

すると左の様な結果が得られます。r8c7に注目すると同じマスにaが二つ入っています。したがってbが真である事がわかります。
今回の例では、aとb二つの色分けで済みましたが、実際はもっと複雑なケースにも対応可能です。

その場合は、例えばa-b, c-dの4色があって、cがab双方と両立不可の場合はdが真であるといったようなロジックを使います。

	Simple Coloring (Simple Chain)やMulti Coloringではある一つの数字候補に注目して色分けを行いました。Advanced Coloring以上のテクニックではColoringの対象は複数の数字候補です。左の問題を例にして試してみたいと思います。この問題はSudoku Susserに例題として載っているMenneske.noの＃1976940 Super Hardです。 (あまり良い例ではなかった。でも他のを試す気力はないので、、、)
	基本的なテクニックを使うと左の状態まで持っていく事ができます。 (本来ならここで59のUnique Rectangleを使うのですが、、、) まず数字候補の2に注目して色分けしてみます。
	左の様に、aとb二つのグループにわけられます。普通のColoringではこの時点でストップですが、Advanced Coloringではさらに色分けを進めます。例えばr2c1に注目すると、このマスは2と3二つの候補をもち、2がaに色分けされています。このマスに2が入らない時、3が確定するので、この3をbで色分けし、今度は3に注目して色分けを進めます。
	すると左の様な結果が得られます。r8c7に注目すると同じマスにaが二つ入っています。したがってbが真である事がわかります。今回の例では、aとb二つの色分けで済みましたが、実際はもっと複雑なケースにも対応可能です。その場合は、例えばa-b, c-dの4色があって、cがab双方と両立不可の場合はdが真であるといったようなロジックを使います。