Rubyでピクロスのソルバ

　最近Ruby1.9.1が出たので、乗り換えついでに久しぶりにプログラミングっぽい話題でもと思い、ピクロスのソルバを書いてみました。

ファイル

• picross.rb
• sample.txt

使い方

ruby picross.rb sample.txt

　と問題ファイルを与えると、

　　｜　　 2 1 1 2　　｜
　　｜　　 1 1 1 1 3 2｜
　　｜ 4 6 2 1 1 2 2 1｜
----＋----------------＋
　 4｜　　　　　　　　｜
 2 2｜　　　　　　　　｜
 2 2｜　　　　　　　　｜
　 8｜　　　　　　　　｜
　 2｜　　　　　　　　｜
 2 2｜　　　　　　　　｜
 2 2｜　　　　　　　　｜
　 4｜　　　　　　　　｜
----＋----------------＋
　　｜　　 2 1 1 2　　｜
　　｜　　 1 1 1 1 3 2｜
　　｜ 4 6 2 1 1 2 2 1｜
----＋----------------＋
　 4｜××■■■■××｜
 2 2｜×■■××■■×｜
 2 2｜■■××××■■｜
　 8｜■■■■■■■■｜
　 2｜■■××××××｜
 2 2｜■■××××■■｜
 2 2｜×■■××■■×｜
　 4｜××■■■■××｜
----＋----------------＋

　のような結果を表示します。解なしなら解なしと判定します。解が一つ以上あれば最初に見つかった解を表示します。複数解になっているかどうかまでは気にしません。

　問題ファイルの形式は、

• 最初の一行が盤面の高さと幅
• 次の行からは、一行ごとに
  • 横のヒントを左から順に並べたものを、上から下に
  • 縦のヒントを上から順に並べたものを、左から右に
• 区切り文字に使えるのは半角のスペースかカンマ

　です。詳しくはサンプル問題のファイルを見て下さい。

ruby picross.rb sample.txt -v

　とオプションをつけると途中経過も表示します。この場合よほど単純な問題でなければ長くなりすぎるので、

ruby picross.rb sample.txt -v > result.txt

　などとして、後で結果を書き出したファイルを見るようにした方がいいでしょう。大きな問題でも時間とRubyの許す限り解けるはずですが、ヒントの数字が3桁に達するような場合は、表示されるのは下2桁の値だけになります。

　ちなみに単純な計算を山ほど行うので、1.9.1では1.8系より目に見えて早くなりました。うちの環境では30×30の広さでも数秒、さらにスカスカの難しそうな問題でもせいぜい30秒程度です。

　あまり巨大なのは問題が見つからなかったので試していませんが、人間が解くことを想定しているような問題なら大体リーズナブルな時間で解けるのではないかと思います。

　また、一番面倒くさかったのは解かせてみる問題を打ち込むことでした。入力した問題があったらメールフォームからでも送っていただけるとありがたいです。もちろん著作権のあるものは公開できませんが。

追記　2/20

　横に細長い問題の扱いでバグがあったので修正しました。

追記　2/24

　途中経過の表示時に「★」マークを出力するようにしました。結果ファイルで「★」を次々に検索するようにすれば簡易アニメーションのように見ることができるようになるはず。

おまけ

　誰が得すんだこのTAS。