201212

Python


おねえさん問題の３次元版

この記事は
日曜数学 Advent Calendar 2020
の12/12 分として書いております。

「nXnXn gird graph の端から端まで、自身と交差することなく、全ての格子点を通る経路」

を数え上げてみた。

私のコードでは3X3X3 gird graph までしか求めることができなかった。

from graphillion import GraphSet

def make_nXnXn_grid_graph(n):
    grids = []
    for x in range(0, n):
        y = x * n * n
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if x < n - 1:
                    grids.append((y + i + (j - 1) * n, y + i + (j - 1) * n + n * n))
                if j < n:
                    grids.append((y + i + (j - 1) * n, y + i + j * n))
        for i in range(1, n * n, n):
            for j in range(1, n):
                grids.append((y + i + j - 1, y + i + j))
    return grids

def A(n):
    universe = make_nXnXn_grid_graph(n)
    GraphSet.set_universe(universe)
    start, goal = 1, n * n * n
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()

print([A(n) for n in range(2, 4)])

出力結果

[6, 38256]