151129

Ruby


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

左右上下に進む場合について
たどり着くy 座標で分類してみた。
（実行時間は3時間ほどかかる。）

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

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

出力結果
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]のとき
m = 0 のとき
[1, [1]]
[1, [0, 1, 0]]
[1, [0, 0, 1, 0, 0]]
[1, [0, 0, 0, 1, 0, 0, 0]]
[1, [0, 0, 0, 0, 1, 0, 0, 0, 0]]
[1, [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]]
[1, [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]]
[1, [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]]
m = 1 のとき
[1, [1]]
[1, [0, 1, 0]]
[3, [0, 1, 1, 1, 0]]
[15, [0, 3, 3, 3, 3, 3, 0]]
[153, [0, 25, 25, 19, 15, 19, 25, 25, 0]]
[4169, [0, 589, 589, 475, 311, 241, 311, 475, 589, 589, 0]]
[346211, [0, 42903, 42903, 35397, 25433, 18503, 15933, 18503, 25433, 35397, 42903, 42903, 0]]
[86336255, [0, 9578225, 9578225, 7879989, 5801937, 4565323, 3908305, 3712247, 3908305, 4565323, 5801937, 7879989, 9578225, 9578225, 0]]
m = 2 のとき
[1, [1]]
[1, [0, 1, 0]]
[9, [0, 3, 3, 3, 0]]
[345, [0, 83, 65, 49, 65, 83, 0]]
[95265, [0, 18039, 14933, 10329, 8663, 10329, 14933, 18039, 0]]
m = 3 のとき
[1, [1]]
[1, [0, 1, 0]]
[29, [0, 10, 9, 10, 0]]
[10199, [0, 2473, 1881, 1491, 1881, 2473, 0]]
[83918867, [0, 15568099, 12387799, 9603105, 8800861, 9603105, 12387799, 15568099, 0]]
m = 4のとき
[1, [1]]
[1, [0, 1, 0]]
[95, [0, 33, 29, 33, 0]]
[317897, [0, 75725, 58651, 49145, 58651, 75725, 0]]
m = 5のとき
[1, [1]]
[1, [0, 1, 0]]
[313, [0, 109, 95, 109, 0]]
[9947973, [0, 2346776, 1836159, 1582103, 1836159, 2346776, 0]]