151128

Ruby


正方形の形をした領域内のSelf-avoiding walk(1)

点の集合Dを
格子点で-n ≦ x ≦ n, -n ≦ y ≦ nを満たしているもの
とする。
今、Dの点(0, 0)から出発し、
自身が通った点を通ることなく、左右上下に進みながら
Dの境界上の格子点のいずれか一つへたどることとする。
このたどり方が何通りあるか出力してみる。

# -*- coding: cp932 -*-

move0 = [[1, 0], [0, 1]]
move1 = [[1, 0], [-1, 0], [0, 1]]
move2 = [[1, 0], [0, 1], [0, -1]]
move3 = [[1, 0], [-1, 0], [0, 1], [0, -1]]

def search(move, x, y, n, used)
  return 0 if n + 1 <= x.abs || n + 1 <= y.abs || used[x + n + (y + n) * (2 * n + 1)]
  return 1 if x.abs == n || y.abs == n
  cnt = 0
  used[x + n + (y + n) * (2 * n + 1)] = true
  move.each{|mo|
    cnt += search(move, x + mo[0], y + mo[1], n, used)
  }
  used[x + n + (y + n) * (2 * n + 1)] = false
  return cnt
end

move = move3
puts "move = #{move3}のとき"
(0..3).each{|n|
  used = Array.new((2 * n + 1) * (2 * n + 1), false)
  p search(move, 0, 0, n, used)
}

出力結果
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]のとき
1
4
92
115516