151128(3)

Ruby


（辺が斜めの）正方形の形をした領域内のSelf-avoiding walk(2)

経路の長さで分けてみる。

# -*- 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, depth)
  ary0 = Array.new((n - 1) * (n - 1) + n * n + 1, 0)
  return ary0 if n + 1 <= (x + y).abs || n + 1 <= (y - x).abs || used[x + n + (y + n) * (2 * n + 1)]
  if (x + y).abs == n || (y - x).abs == n
    ary0[depth] = 1
    return ary0
  end
  c_ary = Array.new((n - 1) * (n - 1) + n * n + 1, 0)
  used[x + n + (y + n) * (2 * n + 1)] = true
  move.each{|mo|
    ary1 = search(move, x + mo[0], y + mo[1], n, used, depth + 1)
    c_ary = (0..(n - 1) * (n - 1) + n * n).map{|i| c_ary[i] + ary1[i]}
  }
  used[x + n + (y + n) * (2 * n + 1)] = false
  return c_ary
end

N = 5
move = move3
puts "move = #{move3}のとき"
(0..N).each{|n|
  used = Array.new((2 * n + 1) * (2 * n + 1), false)
  a_ary = search(move, 0, 0, n, used, 0)
  p [a_ary.inject(:+), a_ary]
}

出力結果
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]のとき
[1, [1, 0]]
[4, [0, 4]]
[12, [0, 0, 12, 0, 0, 0]]
[148, [0, 0, 0, 28, 0, 40, 0, 40, 0, 40, 0, 0, 0, 0]]
[15132, [0, 0, 0, 0, 60, 0, 184, 0, 376, 0, 976, 0, 2072, 0, 3904, 0, 4680, 0, 2880, 0, 0, 0, 0, 0, 0, 0]]
[12269676, [0, 0, 0, 0, 0, 124, 0, 576, 0, 1776, 0, 5592, 0, 19368, 0, 62080, 0, 185208, 0, 496744, 0, 1130232, 0, 2072216, 0, 2868480, 0, 2792536, 0, 1791656, 0, 704600, 0, 138488, 0, 0, 0, 0, 0, 0, 0, 0]]