右折禁止(アルゴリズム・パズル)

アルゴリズム・パズルを Ruby で解いてみました。
20170526124128
 

class TurnLeft
  class Position
    def initialize(x, y)
      @x, @y = x, y
    end
    attr_accessor :x, :y
    
    def +(dir)
      Position.new(@x + dir[0], @y + dir[1])
    end
  end
  
  class Field
    def initialize
      @yoko = Array.new(Height + 1) {Array.new(Width , 0)}
      @tate = Array.new(Width  + 1) {Array.new(Height, 0)}
    end
    
    def set(po, dir)
      if dir[1].zero?
        x = (dir[0] > 0) ? po.x : po.x - 1
        @yoko[po.y][x] = 1
      else
        y = (dir[1] > 0) ? po.y : po.y - 1
        @tate[po.x][y] = 1
      end
    end
    private :set
    
    def get(po, dir)
      if dir[1].zero?
        x = (dir[0] > 0) ? po.x : po.x - 1
        return 1 if x >= Width or x < 0
        a = @yoko[po.y][x]
      else
        y = (dir[1] > 0) ? po.y : po.y - 1
        return 1 if y >= Height or y < 0
        a = @tate[po.x][y]
      end
      set(po, dir) if a.zero?
      a
    end
    
    def dup
      Marshal.load(Marshal.dump(self))
    end
  end
  
  def go
    puts main(Position.new(0, 0), [1, 0], Field.new)
  end
  
  def main(po, dir, field)
    co = 0
    nxt = po + dir
    return 1 if nxt.x == Width and nxt.y == Height   #ゴールか?
    return 0 if nxt.x > Width or nxt.x < 0 or nxt.y > Height or nxt.y < 0
    return 0 unless field.get(po, dir).zero?         #すでに通っているか?
    
    co += main(nxt, dir, field.dup)                  #直進
    co += main(nxt, [-dir[1], dir[0]], field.dup)    #左折
  end
  private :main
end

Width, Height = 6, 4

TurnLeft.new.go

答えは 2760通りです。かかった時間は自分の環境で約 3.7秒でした。


※追記(2018/3/13)
別の方法で解いてみました。

def yoko?(x, y, x1)
  return false if x1 < 0 or x1 > Width
  x2 = [x, x1].min
  return false if @yoko[y][x2] == 1
  x2
end

def tate?(x, y, y1)
  return false if y1 < 0 or y1 > Height
  y2 = [y, y1].min
  return false if @tate[x][y2] == 1
  y2
end

def solve(x, y, dir)
  walk = lambda do |dir|
    dirs = [[1, 0], [0, -1], [-1, 0], [0, 1]]
    x1 = x + dirs[dir][0]
    y1 = y + dirs[dir][1]
    if (dir == 0 or dir == 2) and (x2 = yoko?(x, y, x1))
      @yoko[y][x2] = 1
      solve(x1, y1, dir)
      @yoko[y][x2] = 0
    elsif (dir == 1 or dir == 3) and (y2 = tate?(x, y, y1))
      @tate[x][y2] = 1
      solve(x1, y1, dir)
      @tate[x][y2] = 0
    end
  end
  
  if x == Width and y == 0
    @co += 1
  else
    walk.call(dir)            #直進
    walk.call((dir + 1) % 4)  #左折
  end
end

Width, Height = 6, 4

@yoko = Array.new(Height + 1) {Array.new(Width , 0)}
@tate = Array.new(Width  + 1) {Array.new(Height, 0)}
@co = 0

solve(0, Height, 0)
puts @co    #=>2760

解くのにかかった時間は 0.3秒ほどです。