151125

Ruby


二等辺三角形の形をした領域内のSelf-avoiding walk(1)

点の集合Dを
格子点で0 ≦ x ≦ mn, x / m ≧ y ≧ - x / mを満たしているもの
とする。
今、Dの点(0, 0)から出発し、
自身が通った点を通ることなく、右か、上下に進みながら
(mn, n - 1), (mn, n -2), … , (mn, -(n - 1))
のいずれか一つへたどることとする。
このたどり方は
n > 0のとき、
(1 × 3 × 5× … × (2n - 1))^m
通りあるがこれを確かめてみる。

# -*- 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, m, n, used)
  return 0 if x < 0 || m * n + 1 <= x || - m * y > x || m * y > x || used[x + (y + n) * (m * n + 1)]
  return 1 if x == m * n
  cnt = 0
  used[x + (y + n) * (m * n + 1)] = true
  move.each{|mo|
    cnt += search(move, x + mo[0], y + mo[1], m, n, used)
  }
  used[x + (y + n) * (m * n + 1)] = false
  return cnt
end

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

出力結果
move = [[1, 0], [0, 1], [0, -1]]のとき
m = 0 のとき
1
1
1
1
1
1
1
1
1
1
m = 1 のとき
1
1
3
15
105
945
10395
135135
2027025
34459425
m = 2 のとき
1
1
9
225
11025
893025
108056025
m = 3 のとき
1
1
27
3375
1157625