イラストロジック自動解答

たまには趣味のコードとか。って、いっつも趣味のことしか書いてないやんというツッコミはおいといて。


以前も Erlang で倉庫番ソルバーを書いたり、時折無性にパズルを解くコードを書きたくなるんだけど、今回はイラストロジックを解いてみた(お絵かきロジック、お絵かきパズル、ののぐらむ、ピクロスなど同じものを指す名前多数)。
実は大昔に一度書いたことがあるんだけど、まだ20世紀だった頃に Ko-Window(X68000) のアセンブラでという話なので、動かせないわ*1読めないわ。


というわけで Rubyで、極力短くなるように書いてみたものを末尾に掲げてある。ソルバー部分で100行未満になったから、まあまあ短い? each_slice とか初めて使ったし。
可読性を大きく損なう書き方をすれば行数はまだまだいくらでも減らせるけど、さすがにそれは本意ではないから。
速度は速くない。このコードに 30x30 くらいの問題を解かせたら、新しめの PC でも2秒くらいかかる。無駄な探索をまじめに削ればいくらでも速くなるが、そうするとどうしてもコード量が増えるのでやめといた。*2


問題データはテキストファイルで与える。
横のヒント、縦のヒントの順でその区切りには "--" を書く。各行ごとに数値を空白区切りで記し、行は改行で区切る。塗りつぶすマスがない行は 0 を1つだけ書く。
Wikipedia で紹介されている右図の例題の場合は次のようになる

http://upload.wikimedia.org/wikipedia/ja/f/f0/Paint_by_numbers_ex01.png

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

*1:x68kエミュあるけどめんどくさいよね

*2:書いたけど削った

*3:消去法を使わないと解けないのは人間には難しくなりすぎるだろうからか、解は1つしか無いけど消去法を使わないと解けない問題を作ることが単純に難しいからか。

*4:完了チェックはまじめにやってないのでミスがあってもスルーするかも