150910

Ruby

Number of knight's tours on a 3×k chessboard(2)

Cに比べて遅いため、h = 14 までしか計算していない。

@knight_move =
[[2, -1], [2, 1], [-2, -1], [-2, 1],
[1, -2], [1, 2], [-1, -2], [-1, 2]]

# startが[x, y]
def search(x, y, w, h, used, depth)
  return 0 if x < 0 || w <= x || y < 0 || h <= y || used[x + y * w]
  return 1 if depth == w * h
  cnt = 0
  used[x + y * w] = true
  @knight_move.each{|m|
    cnt += search(x + m[0], y + m[1], w, h, used, depth + 1)
  }
  used[x + y * w] = false
  return cnt
end

def directed_open_tours3(h)
  return 0 if h < 3
  total = 0
  (0..h / 2 - 1).each{|y|
    used = Array.new(3 * h, false)
    total += search(0, y, 3, h, used, 1) * 4
    p [y, 0, total]
    used = Array.new(3 * h, false)
    total += search(1, y, 3, h, used, 1) * 2
    p [y, 1, total]
  }
  if h % 2 == 1
    y = h / 2
    used = Array.new(3 * h, false)
    total += search(0, y, 3, h, used, 1) * 2
    used = Array.new(3 * h, false)
    total += search(1, y, 3, h, used, 1) * 1
  end
  total
end

(1..14).each{|h|
  p directed_open_tours3(h)
}

出力結果

0

0

[0, 0, 0]

[0, 1, 0]

0

[0, 0, 8]

[0, 1, 16]

[1, 0, 16]

[1, 1, 16]

16

[0, 0, 0]

[0, 1, 0]

[1, 0, 0]

[1, 1, 0]

0

[0, 0, 0]

[0, 1, 0]

[1, 0, 0]

[1, 1, 0]

[2, 0, 0]

[2, 1, 0]

0

[0, 0, 32]

[0, 1, 32]

[1, 0, 32]

[1, 1, 88]

[2, 0, 104]

[2, 1, 104]

104

[0, 0, 328]

[0, 1, 464]

[1, 0, 544]

[1, 1, 640]

[2, 0, 656]

[2, 1, 656]

[3, 0, 752]

[3, 1, 792]

792

[0, 0, 688]

[0, 1, 688]

[1, 0, 688]

[1, 1, 880]

[2, 0, 912]

[2, 1, 912]

[3, 0, 912]

[3, 1, 992]

1120

[0, 0, 1792]

[0, 1, 2816]

[1, 0, 3440]

[1, 1, 4272]

[2, 0, 4464]

[2, 1, 4528]

[3, 0, 4784]

[3, 1, 4944]

[4, 0, 5584]

[4, 1, 6096]

6096

[0, 0, 10416]

[0, 1, 10416]

[1, 0, 10416]

[1, 1, 14416]

[2, 0, 15584]

[2, 1, 15584]

[3, 0, 15584]

[3, 1, 16624]

[4, 0, 20224]

[4, 1, 20224]

21344

[0, 0, 38632]

[0, 1, 51320]

[1, 0, 58840]

[1, 1, 70072]

[2, 0, 73880]

[2, 1, 74584]

[3, 0, 80360]

[3, 1, 84544]

[4, 0, 97168]

[4, 1, 102592]

[5, 0, 110144]

[5, 1, 114496]

114496

[0, 0, 121968]

[0, 1, 121968]

[1, 0, 121968]

[1, 1, 158800]

[2, 0, 167664]

[2, 1, 167664]

[3, 0, 167664]

[3, 1, 180416]

[4, 0, 223168]

[4, 1, 223168]

[5, 0, 223168]

[5, 1, 243456]

257728

[0, 0, 412512]

[0, 1, 528176]

[1, 0, 597840]

[1, 1, 727952]

[2, 0, 762928]

[2, 1, 769072]

[3, 0, 813936]

[3, 1, 853040]

[4, 0, 988656]

[4, 1, 1040560]

[5, 0, 1116400]

[5, 1, 1177232]

[6, 0, 1257680]

[6, 1, 1292544]

1292544