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

アルゴリズム・パズルを 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秒でした。