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秒ほどです。
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問
- 作者: 増井敏克
- 出版社/メーカー: 翔泳社
- 発売日: 2015/10/16
- メディア: Kindle版
- この商品を含むブログ (9件) を見る
