たまには趣味のコードとか。って、いっつも趣味のことしか書いてないやんというツッコミはおいといて。
以前も Erlang で倉庫番ソルバーを書いたり、時折無性にパズルを解くコードを書きたくなるんだけど、今回はイラストロジックを解いてみた(お絵かきロジック、お絵かきパズル、ののぐらむ、ピクロスなど同じものを指す名前多数)。
実は大昔に一度書いたことがあるんだけど、まだ20世紀だった頃に Ko-Window(X68000) のアセンブラでという話なので、動かせないわ*1読めないわ。
というわけで Rubyで、極力短くなるように書いてみたものを末尾に掲げてある。ソルバー部分で100行未満になったから、まあまあ短い? each_slice とか初めて使ったし。
可読性を大きく損なう書き方をすれば行数はまだまだいくらでも減らせるけど、さすがにそれは本意ではないから。
速度は速くない。このコードに 30x30 くらいの問題を解かせたら、新しめの PC でも2秒くらいかかる。無駄な探索をまじめに削ればいくらでも速くなるが、そうするとどうしてもコード量が増えるのでやめといた。*2
問題データはテキストファイルで与える。
横のヒント、縦のヒントの順でその区切りには "--" を書く。各行ごとに数値を空白区切りで記し、行は改行で区切る。塗りつぶすマスがない行は 0 を1つだけ書く。
Wikipedia で紹介されている右図の例題の場合は次のようになる
4 2 2 2 2 8 2 2 2 2 2 4 -- 4 6 2 1 2 1 1 1 1 1 1 2 1 2 3 2 2 1
実行すると結果が次のように表示される。イラストロジックでは空白が確定した場所には×を記すのが一般的だが、結果の見やすさを考えて□を使っている。
□□■■■■□□ □■■□□■■□ ■■□□□□■■ ■■■■■■■■ ■■□□□□□□ ■■□□□□■■ □■■□□■■□ □□■■■■□□
Wikipedia の記事にてイラストロジックの解き方が解説されているが、その中の「消去法」以外の推論はすべて入っている。つまり行単位の推論は完全に行える。
「消去法」は複数行を同時に推論しないと解けない問題や、解が複数ある問題には必要になるので、それらの問題をこのコードに与えると、解答が途中で終わってしまい空白が残ったままの結果が出力される。
消去法は実はそんなに難しくはないが、試行数がめちゃめちゃ増えるのでパス。まあ、よくあるパズル雑誌の問題は解が複数あるなんて絶対にないし、行単位の推論で必ず解けるようになっているっぽいので、このコードでも大丈夫。*3
一方、投稿サイトとかの問題は解が複数あるものも珍しくないので注意。
あと、問題にミスがあると☆が出力されることがある。*4
ここからコード。
#!/usr/bin/env ruby # -*- encoding: utf-8 -*- class Searcher WHITE = 1 BLACK = 2 CHARS = [" ", "□", "■", "☆"] def initialize(states, hints) @states = states @hints = hints @size = states.length occupation = hints.inject(:+) + hints.length - 1 raise "too large hint" if occupation > @size @free_width = @size - occupation end def search return Array.new(@size){WHITE} if @hints[0] == 0 @whites = Array.new(@size){WHITE} @blacks = Array.new(@size){BLACK} search_sub [], 0, 0 @blacks.zip(@whites).map {|x, y| x | y} end def search_sub(pos_list, free_idx, current_pos) cur_hint = @hints[pos_list.length] (free_idx..@free_width).each do |f| pos = current_pos + f - free_idx break if pos > 0 && @states[pos - 1] == BLACK next if @states[pos, cur_hint].member?(WHITE) new_pos_list = pos_list + [pos] end_pos = pos + cur_hint if new_pos_list.length < @hints.length search_sub new_pos_list, f, end_pos + 1 elsif !@states[end_pos..-1].member?(BLACK) pos = 0 @hints.zip(new_pos_list) do |cur_hint, cur_pos| @blacks.fill 0, pos..cur_pos-1 if cur_pos > 0 @whites.fill 0, cur_pos, cur_hint pos = cur_pos + cur_hint end @blacks.fill 0, pos..-1 if pos < @size end end end end class Solver def initialize(horiz, verti) sum_horiz = horiz.flatten.inject(0, :+) sum_verti = verti.flatten.inject(0, :+) raise "horizontal and vertical total isn't equal" if sum_horiz != sum_verti @horiz = horiz @verti = verti @width = verti.length @height = horiz.length @fields = Array.new(@width * @height){0} end def solve flag = true while flag flag = false @height.times do |i| flag = solve_sub(i * @width, @width, 1, @horiz[i]) || flag end @width.times do |i| flag = solve_sub(i, @height, @width, @verti[i]) || flag end end end def solve_sub(offset, size, step, hint) states = (0..size-1).map{|i| @fields[offset + i * step]} return false unless states.member?(0) result = Searcher.new(states, hint).search if states != result size.times do |i| @fields[offset + i * step] |= result[i] end true end end def printField puts "−" * @width @fields.each_slice(@width) do |s| puts s.map{|x| Searcher::CHARS[x]}.join("") end end end def load_data(data) list = [] data.each_line do |line| break if line =~ /^-/ if line =~ /^([0-9]+\s)*[0-9]+$/ list << line.split.map{|x| x.to_i} end end list end if $0 == __FILE__ solver = open(ARGV[0], "r:utf-8") do |f| horiz = load_data(f) verti = load_data(f) Solver.new(horiz, verti) end solver.solve #true solver.printField end