倉庫番ソルバー（Brute Force）

sokoban_solver.rb

module Sokoban
  Pos = Struct.new(:x, :y) do
    def dirs
      [Pos.new(x + 1, y), Pos.new(x, y - 1),
       Pos.new(x - 1, y), Pos.new(x, y + 1)]
    end
    
    def inspect = "<#{x},#{y}>"
    def over_there(e) = Pos.new(2 * e.x - x, 2 * e.y - y)
    def <=>(a) = [x, y] <=> [a.x, a.y]
  end
  
  module Disp
    def self.show(raw)
      puts raw
      sleep(1)
    end
  end
  
  class Field
    class Node
      def initialize(pos, parent=nil)
        @pos = pos
        @parent = parent
      end
      attr_reader :pos, :parent
      
      def x = @pos.x
      def y = @pos.y
      def dirs = @pos.dirs.map { Node.new(_1, self) }
    end  #----Node
    
    def initialize(data)
      @raw = data
      width = data[0].length
      
      d = data.join
      i = d.index("@")
      xy = ->(idx) { Pos.new(idx % width, idx / width) }
      @man = xy.(i)
      @raw[@man.y][@man.x] = " "
      
      @goals =
        d.each_char.with_index.filter_map { |c, i| c == "." ? xy.(i) : nil }
      @boxes =
        d.each_char.with_index.filter_map { |c, i| c == "=" ? xy.(i) : nil }
      @goals.sort!
      @boxes.sort!
        
      @raw.map! { _1.tr(".", " ") }
    end
    attr_reader :boxes, :man, :raw
    attr_writer :goals
    
    def reachable?(from, to, flag = true)
      return [from] if from == to
      f = @raw.map(&:dup)
      queue = [Node.new(from)]
      try = ->{
        while (now = queue.shift)
          now.dirs.each do |nxt|
            next unless f[nxt.y][nxt.x] == " " || f[nxt.y][nxt.x] == "."
            if to == nxt.pos
              if flag
                path = []
                a = nxt
                while a
                  path.unshift(a.pos)
                  a = a.parent
                end
                return path
              else
                return true
              end
            else
              queue << nxt
              f[nxt.y][nxt.x] = "$"
            end
          end
        end
        false
      }
      try.()
    end
    
    def walk
      @boxes.each do |b|
        b.dirs.select { |b1| @raw[b1.y][b1.x] == " " }.each do |man|
          ov = man.over_there(b)
          next unless @raw[ov.y][ov.x] == " "
          next unless (path = reachable?(@man, man))
          yield(man, b, path)
        end
      end
    end
    
    def push(man, box)
      raw = @raw.map(&:dup)
      raw[box.y][box.x] = "@"
      
      raw[man.y][man.x] = " "
      boxes = @boxes.reject { _1 == box } + [man.over_there(box)]
      boxes.sort!
      boxes.each { |b| raw[b.y][b.x] = "=" }
      
      f = Field.new(raw)
      f.goals = @goals
      f
    end
    
    def to_s
      raw = @raw.map(&:dup)
      @goals.each { |g| raw[g.y][g.x] = "." }
      @boxes.each { |b| raw[b.y][b.x] = "=" }
      raw[@man.y][@man.x] = "@"
      raw
    end
    
    def show(path)
      raw = to_s
      a = path[0]
      raw[a.y][a.x] = " "
      path[1..-1].each do |b|
        raw[b.y][b.x] = "@"
        Disp.show(raw)
        raw[b.y][b.x] = " "
      end
    end
    
    def goal? = @goals == @boxes
  end  #----Field
  
  class History
    @@all_history = {}
    def initialize(*arg)
      case arg
      in [Field => field]
        @@all_history[field.boxes] = field.man
        @progress = [[field, []]]
      in [history, field, path]
        @progress = history.progress + [[field, path]]
      end
    end
    attr_reader :progress
    
    def add(next_field, path)
      man = next_field.man
      boxes = next_field.boxes
      found = @@all_history[boxes]
      if found
        case found
        in Array => men
          f = men.any? { |man0| next_field.reachable?(man0, man, false) }
          return nil if f
          @@all_history[boxes] << man
        in Pos => man0
          g = next_field.reachable?(man0, man, false)
          return nil if g
          @@all_history[boxes] = [man0, man]
        end
      else
        @@all_history[boxes] = man
      end
      History.new(self, next_field, path)
    end
    
    def finish
      e = @progress.to_enum
      field, _ = e.next
      Disp.show(field.to_s)
      loop do
        f, path = e.next
        field.show(path)
        field = f
        Disp.show(field.to_s)
      end
    end
  end  #----History
  
  module_function
  
  def solve(data)
    field = Field.new(data)
    try(field, History.new(field))
  end
  
  def try(field, history)
    if field.goal?
      history.finish
      true
    else
      field.walk do |man, box, path|
        next_field = field.push(man, box)
        new_history = history.add(next_field, path)
        next unless new_history
        f = try(next_field, new_history)
        return f if f
      end
      false
    end
  end
end

Sokoban.solve(DATA.readlines(chomp: true))

__END__
#######
#   ###
#  = ##
# =@= #
#  == #
#.....#
#######