数独ソルバーを書いてみました。
http://pa-n.sakura.ne.jp/200712/sudoku/
いきさつ
あーPS3買ったのにやりたいゲームないなー
↓
体験版やるか
↓
GT5 prologue体験版も飽きたなー
てか、prologueの体験版かー
GT5は来年12月って.....
↓
レミング........
↓
ぽちゃぽちゃあひるちゃん.............（買った \840）
↓
.................
↓
カズオ........
他の数独ソルバーのアルゴリズム
http://www.sudoku.name/sudoku-solver/jp
- 解いている様子が見れるのでおもしろい
http://d.hatena.ne.jp/bellbind/20060712/1152692054
- 改良版はコードが簡潔
- 再帰をうまく使っている
http://www.ecclestoad.co.uk/blog/2005/06/02/sudoku_solver_in_three_lines_explained.html
- コードが簡潔
- 再帰をうまく使っている
http://echoo.yubitoma.or.jp/weblog/MASA-WA/eid/520627
- コードは公開されていない？
ところで、これらの（コード公開の）ソルバーには次の共通点があります。
- どのマスを仮定するかを決める際、候補の少なさを基準にしていない
- 左上から右下にみていって、空白だったら確定マスに矛盾しないように仮定する
これをちょっと変更して、今回自分が書いたやつみたいに、「候補が少ないところを優先して仮定する」ようにすることで、
空白マスがたくさんある（＝仮定がたくさん必要な）問題に対しては目に見えて高速に解けるようになります。
直感的には、次の２つのループ回数
（外側）9×9×9×...×9×8×5×2（内側）
と
（外側）2×5×8×9×...×9×9×9（内側）
との違いといいますか。（ループ回数はイメージです）
ループの内側にいくにしたがって、仮定したことによる候補の絞りこみで結構すぐに矛盾があらわになりがちだと思うんですね。
なので、最外ループの反復回数が少ないと、わりとすぐに探索木が半分になったりするわけです。