150904

Ruby


桂馬飛び

スタートからゴールまで桂馬飛びで何手で行けるか求めるコードを書いてみた。

def moveknight(point, board)
  c, r = point
  points =
  [[c + 2, r - 1], [c + 2, r + 1], [c - 2, r - 1], [c - 2, r + 1],
  [c + 1, r - 2], [c + 1, r + 2], [c - 1, r - 2], [c - 1, r + 2]]
  points & board
end

def f(start, goal, board)
  return 0 if start == goal
  used = []
  ary = [start]
  used += ary
  next_ary = []
  ary.each{|i| next_ary |= moveknight(i, board)}
  m = 1
  while !next_ary.include?(goal)
    ary = next_ary
    used += ary
    next_ary = []
    ary.each{|i| next_ary |= moveknight(i, board)}
    # すでに通った場所は除く
    next_ary -= used
    m += 1
  end
  m
end

n = 50
board = (1..n).to_a.product((1..n).to_a)
p f([1, 1], [3, 2], board)
p f([1, 1], [n, n], board)

出力結果
1
34