無駄に数独を解くアルゴリズムを考えた話。

暇つぶしにrubyで書いた（といっても、ここには今のところコードを載せないし、rubyを使ったのは、Array周りで楽するためだけ。)


1.候補を列挙して確定した値を埋める関数
すべてのマス（i,j）について、（i,j）が属する行、列、ブロックの数字を参照して、(i,j)に入る値の候補すべてを配列Aに格納する。このとき、(i,j)に入る値の候補がただ一つに決まるときは、(i,j)
に入る値を確定する。
（(i,j)に数字がすでに入っているとき、(i,j)に入る候補が存在しない時は、空の配列を入れる。）
すべてのマスが埋まったら、正解の状態として記憶する。
この処理を候補を入れる配列Aが変わらなくなるまで繰り返す。(←終わらない場合があるかもしれない。検証してない。)

2.メインループ
・適当に初期化してから、１.の関数に入る。
・すべてのマス(i,j)について、順に以下の処理を行う。
　すでに値が埋まっていれば次のマスの処理へ。
　このときのマスの状態、数字の候補の配列Aを記憶
　値の候補が入っている配列A(i,j)から値を選んで仮に入れる。
　1.の関数の処理へ。
　次のマスの処理へ。
　戻ってきたら、数字の候補、マスの状態を戻す。
（途中で矛盾が出たら関数から抜けて、勝手に矛盾があったところまで戻ってくる。）


で、複数回答がある場合もすべての正解の状態が記憶されるはず。
あとは、こまごまとした、解けたかどうかを判別したり、矛盾が起きてないかを判別する関数とかを用意した。

そもそも、サンプルとして食わせるために適当に用意した数独が、解答が一通りに定まるまともな数独じゃなかったので、そこあたりですべて解答として列挙するのに苦労した。解答を一通り見つければ終わり、というアルゴリズムなら、バックトラック法、でググればコードがすぐに出てくるし、そちらの方が賢いかもしれない。

ちょっとアルゴリズムを工夫できるかもしれない。たとえば入る数字の候補の配列Aの同じブロックを見て(1,2,3),(2,3),(2,3)が候補になるような3点があったとすると、はじめのマスは1に確定する。(でも、2とかを入れてみればすぐに矛盾とわかる、、、)これをやるには、行、列、ブロックのそれぞれで全部ループを回さして探索しないといけないから、実際にやってみないと速いかどうかはわからない。というか、遅いかも?