いわゆる「スライドパズル（15パズル）」もどきを Ruby で解いてみる

スライドパズルっていうおもちゃがありますよね。4×4 のマス目に空白がひとつあって（残りはコマ）、コマは空白にスライドさせて動かすしかなく、それを特定のパターンに揃えるというものです。ここではルールを少し改変して、特定のマスを別の特定のマスに移動させるのに最短で何手かかるかを考えます。

例えば 3×2 のパズルでいちばん右下のマスが空白であり、いちばん左上のマスにあるコマをいちばん右下へもってくるには、最短で 9手かかります。

●●●
● ○

●●●
●○ 

●● 
●○●

● ●
●○●

●○●
● ●

●○●
 ●●

 ○●
●●●

○ ●
●●●

○● 
●●●

○●●
●● 

9手で終了

ただしこれは、下の方から見ていって下さい（プログラムの関係でそうなっています）。

僕が見たアルゴリズムパズルの本では、10×10 のパズルでやるのと同等な問題が与えてありました（駐車場で車を脱出させるという体裁になっていました）。これは自分の書いたプログラムだと、69手ということになります（調べたパターンの数は 8927個）。計算時間はこれだと（自分の環境で）およそ 41秒と、かなり微妙な数字になりました。瞬殺は無理でしたね。これ以上広いパズルだと、根本から考えなおさないとダメかも知れません。

コードは以下です。幅優先探索で求めています。また、既に出たパターンに逢着した場合はスキップしています。

class Parking
  def initialize
    start = Pattern.new
    start.car.x, start.car.y = 0, 0
    start.space.x, start.space.y = Width - 1, Height - 1
    @@patterns = [start]
  end
  
  def solve
    buffer = @@patterns.dup
    while (po = buffer.shift)
      [po.up, po.down, po.left, po.right].each do |i|
        next unless i
        if i[1]    #true ならば終了
          @@co = 0
          i[0].show
          puts "#{@@co - 1}手で終了"
          puts "調べたパターン数は#{@@patterns.size}"
          exit
        end
        buffer << i[0]
      end
    end
  end
end

class Pattern < Parking
  class Car   < Struct.new(:x, :y); end
  class Space < Struct.new(:x, :y); end
  
  def initialize
    @car   = Car.new
    @space = Space.new
    @parent = nil
  end
  attr_accessor :car, :space, :parent
  
  def up
    x, y = space.x, space.y - 1
    return false if y < 0
    check(x, y)
  end
  
  def down
    x, y = space.x, space.y + 1
    return false if y >= Height
    check(x, y)
  end
  
  def left
    x, y = space.x - 1, space.y
    return false if x < 0
    check(x, y)
  end
  
  def right
    x, y = space.x + 1, space.y
    return false if x >= Width
    check(x, y)
  end
  
  def check(x, y)
    nxt = Pattern.new
    nxt.space.x, nxt.space.y = x, y
    nxt.car = (@car.x == x and @car.y == y) ? @space : @car
    
    @@patterns.each do |pa|
      return false if nxt.car == pa.car and nxt.space == pa.space 
    end
    nxt.parent = self
    
    @@patterns << nxt
    [nxt, (nxt.car.x == Width - 1 and nxt.car.y == Height - 1)]
  end
  private :check
  
  def putout
    Height.times do |i|
      st = "●" * Width
      st[@car.x]   = "○" if @car.y   == i
      st[@space.x] = " " if @space.y == i
      puts st
    end
    puts
  end
  
  def show
    @@co += 1
    putout
    @parent.show if @parent
  end
  
  def inspect
    "<Pattern:car(#{@car.x},#{@car.y}), space(#{@space.x},#{@space.y})>"
  end
end

Width = 4; Height = 4

Parking.new.solve