実家に帰ったら、婆さんが数独にはまってた。ボケ防止にいいらしい。ちょうどいいので、flashの数独をgoogleで適当に探してきてお気に入りに登録しておいてやったら喜ばれたヨ。まぁ、使うかどうかわからんけど。
ちょうど、Highr Order Perl読み始めたところだし、家に戻ってきて、数独ソルバでも書いてみるかと思ってたら、タイミングよくUno, dos, tres, quatro!にエントリが。
Higher-Order Perl: Transforming Programs with ProgramsMark Jason Dominus
Morgan Kaufmann / 6402円 ( 2005-03-28 )
バックトラック法ってのを使えばいいのねと自分で書いてみたのはマス目を一つ一つ移動してくコードだったんだけど、再帰深すぎるヨっていうエラーを吐いて終了。なんかダメダメだなぁ。他の人のを読んでみるとまだ埋まってないマス目を再帰で埋めていくべきだったことに気付いた。ちょっとこれに引っ張られたかなと反省。
まだ埋まってないマス目の配列と、過程として数字を置いたマス目の配列の二つを用意して、バックトラック法で解くというわけですな。
とか、わかった上で、三行数独ソルバを読むと、説明もついてるしよくわかった、素敵。
家のマシンで三行数独ソルバを実行してみるとこんな感じ。
$ time perl sudoku.pl < sample 825169734 463857921 917234658 684712593 759386142 231495867 548621379 376948215 192573486 #本当はココまで一行で出力 real 0m1.439s user 0m1.436s sys 0m0.004s
プログラム・プロムナードにhaskellの数独ソルバが載ってたのでそれも実行してみた。ちゃんと理解しないといけないと思いつつ、今回はコピペ。ghciで計算させた。
*Main> sudoku sample [8 2 5 1 6 9 7 3 4 4 6 3 8 5 7 9 2 1 9 1 7 2 3 4 6 5 8 6 8 4 7 1 2 5 9 3 7 5 9 3 8 6 1 4 2 2 3 1 4 9 5 8 6 7 5 4 8 6 2 1 3 7 9 3 7 6 9 4 8 2 1 5 1 9 2 5 7 3 4 8 6 ] (0.28 secs, 26584692 bytes)
haskellもperlクイズみたいなのを誰かやってくれたら嬉しいナァ。とか。