ナンプレの解き方のアルゴリズム

ＧＷで実家に帰ったとき、父がナンプレにハマッってました。
数独とも言われるパズルです。数独はどっかの商標かな。

私自身は、そんなに解いたことはありません。多くて10題くらいでしょう。
父が解いてるのを見て、コンピュータで解くための
解法アルゴリズムを考えてしまう辺りが私の性（さが）なんでしょう。

ナンプレ。まぁご存知だとは思いますが簡単にルールを言うと
・９＊９のマス目に数字を入れる。数字は１～９。
・３＊３のブロックでマス目を９グループに区切る。
・縦横、そして３＊３のグループ内に同じ数は入らない。
こんな感じかな？

で、解法なんですが、全部頭の中で考えただけなので検証まったくしてません。
だから間違ってるかもｗ

１）総当り法
　全てのマス目に数字を入れるパターンを全部調べる。
　９＊９のマス目それぞれに１～９が入るので、９＾８１通り？
　時間さえ掛ければ必ず解けるはず。
　でも美しくない！バーッド！

２）仮置き法
　父が問題を解くプログラムを見たことがあると言ってました。
　左上から右に順番にルールに適合する範囲で数字を仮置きしていくもの。
　右端まで行ったら一段下がってまた右端まで。
　ルールに適合する数字が無いなら、直前のマスの数字が間違っている。
　この場合は一つ戻ってやり直し。
　当然、ドンドン戻る場合もあります。
　総当りでは全部置いてから整合性チェックしてましたが
　こっちは置きながらチェック。
　判定しないパターンがあるから、総当りよりは短時間で
　これも必ず解けるはず。でもこれも美しくない。

３）消去法
　普通の人が問題を解く場合の考え方はこれでしょう。
　あるマス目に着目して、そのマス目に「入らない」数字を調べる。
　入らない数字が８個なら、そのマス目に入るのは残り１つの数字になります。
　で、どうやって消去していくか、というのが重要なのです。

３－１）位置類推法
　同じ数字同士を比較して、位置を類推する方法です。
　例えば、同じ数字が８個あれば残り１個の場所は決まります。
　もっと狭く言うと、左上のブロックに「１」が無く
　中上、右上、左中、左下の４つのブロックに「１」があれば
　左上の「１」の場所は確定します。
　一見、消去法に見えませんが、４つの「１」から左上のブロックでは
　８マスが「１」の可能性が消去されています。

　３）の消去法はマス目に対して「唯一」の解が決定する場合なら解けます。
　ただし、唯一に決定しない場合は解けない。
　
４）グループ類推法
　分かりにくいので、例を挙げて説明。
　同じ３＊３マスのブロック内とします。
　左上のマス目の数字候補が｛1,2｝、右上の数字候補が｛1,2｝
　左下の候補が｛1,2,3｝。
　この情報から、左下は３だと分かります。

　これを一般化すると…、
　同じグループ内（ブロック・縦・横問わず）において
　数字n個による同じ組み合わせ候補（Ａ群とする）がn+1個マス目にある場合
　そのマス目の中で候補がＡ群以外に唯一存在する場合（bとする）は、
　bがそのマス目の解である。
　こんなところでしょうか。
　
　この方法を使っても解けない問題はあるでしょう。
　どんな問題になるかは分かりません。
　（問題としてどうか、という議論はありますが）
　回転・鏡像・可換な問題は本質が同じなのに複数の表現があることになるので
　その場合は、これだけでは解けないことになります。

　極端な例として中央１マスにしか数字が無い場合を考える。
　ある解が見つかったとして…
　　９０度回転させても、やはり解としては正しい⇒回転
　　左右反転させても、やはり解としては正しい⇒鏡像
　　左右の３ブロックずつをまるごと入れ替えても（略）⇒可換

　このチェックは面倒ですね。保留とします。

以上の方法を組み合わせて、解法を考える。
　①マス目を（３）の方法で埋めていく。
　②①により唯一の数字が決まるマス目がなくなるまで繰り返す。
　③（３）で埋まるマス目が無い場合、（４）の方法でマス目を埋める。
　④１つ埋めた状態から①に戻って再度埋めていく。
　⑤③でも一つも埋めることが出来ない場合、さぁどうしよう。

　空いてるマス目に対し、ここから仮置き法を行う。
　多分、これで解けはするはず。

　でも、まだエレガントな方法があるんじゃないかなぁ。
　そこで仮置き法を行う順番を工夫するという手を考える。
　（左上からではなく、解候補が少ないマス目から置くとか）

　うん、少しそれを考えてみよう。
　⑥解候補数が最も小さいマス目を調べる（必然的に候補数は２以上）。　
　⑦数字を仮置き。
　⑧＝①’マス目を（３）の方法で埋めていく。
　⑨＝②’①’により唯一の数字が決まるマス目がなくなるまで繰り返す。
　　ただし、矛盾が発生した場合は、⑦で置いた数字が間違っていたことになる。
　　別の数字の仮置きをして⑧に戻る。
　⑩＝③’（４）の方法でマス目を埋める。
　　ただし、矛盾が発生した場合は、⑦で置いた数字が間違っていたことになる。
　　別の数字の仮置きをして⑧に戻る。
　⑪＝④’その状態から①’に戻って再度埋めていく。
　⑫③’でも一つも埋めることが出来ない場合、さぁどうしよう。

　仮置きにレベルを考える。
　⑦の仮置きをレベル１とし、⑬の仮置きをレベル２とする。
　⑦～⑪と同様のプロセスを仮置きレベルを上げて⑬～⑰で行う。
　矛盾があれば⑬に戻る。⑬で全ての候補が誤りであることが分かれば
　仮置きレベルを一つ下げて、その仮置き（ここでは⑦）が誤りだったと判断する。
　
　ルールに従った単純な仮置きよりも
　仮置きで確定できる情報を一通り精査して真偽を確認したほうが
　エレガントな気がします。

　あ～眠い。この文章ちゃんとまとまってるのかなぁ？
　脳内シミュレーションしかしてないので間違い指摘歓迎。