Python
Number of closed Knight's tours on a m X n board
m = 3, 4, 5, 6 のときを出力してみた。
from graphillion import GraphSet
# (n > 3 and k > 2) or (n > 2 and k > 3)
def make_nXk_knight_graph(n, k):
grids = []
for i in range(1, k + 1):
for j in range(1, n - 1):
if i < k:
grids.append((i + (j - 1) * k, i + (j + 1) * k + 1))
if i > 1:
grids.append((i + (j - 1) * k, i + (j + 1) * k - 1))
for i in range(1, k * n, k):
for j in range(1, k - 1):
if i < k * (n - 1):
grids.append((i + j - 1, i + j + 1 + k))
if i > k:
grids.append((i + j - 1, i + j + 1 - k))
return grids
def A(n, k):
if n == 3 and k == 3: return 0
universe = make_nXk_knight_graph(n, k)
GraphSet.set_universe(universe)
cycles = GraphSet.cycles(is_hamilton=True)
return cycles.len()
print([A(3, n) for n in range(3, 30)])
print([A(4, n) for n in range(3, 20)])
print([A(5, n) for n in range(3, 10)])
print([A(6, n) for n in range(3, 8)])
出力結果
[0, 0, 0, 0, 0, 0, 0, 16, 0, 176, 0, 1536, 0, 15424, 0, 147728, 0, 1448416, 0, 14060048, 0, 136947616, 0, 1332257856, 0, 12965578752, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 8, 0, 44202, 0]
[0, 0, 8, 9862, 1067638]
