Я знаю, что этот вопрос старый, но я ответил на него в другом вопросе (до того, как найти этот вопрос) с помощью метода грубой силы в python, поэтому добавим его сюда для потомков:
pegs = {
1: {3:2, 7:4, 9:5},
2: {8:5},
3: {1:2, 7:5, 9:6},
4: {6:5},
5: {},
6: {4:5},
7: {1:4, 3:5, 9:8},
8: {2:5},
9: {1:5, 3:6, 7:8}
}
def next_steps(path):
return (n for n in range(1,10) if (not path or n not in path and
(n not in pegs[path[-1]]
or pegs[path[-1]][n] in path)))
def patterns(path, steps, verbose=False):
if steps == 0:
if verbose: print(path)
return 1
return sum(patterns(path+[n], steps-1) for n in next_steps(path))
Таким образом, вы можете перечислить все количество шаблонов для любого количества шагов:
>>> [(steps, patterns([], steps)) for steps in range(1,10)]
[(1, 9),
(2, 56),
(3, 320),
(4, 1624),
(5, 7152),
(6, 26016),
(7, 72912),
(8, 140704),
(9, 140704)]
>>> sum(patterns([], steps) for steps in range(4,10))
389112
Это не самый эффективный способ решения этой проблемы, поскольку вы можете использовать отражения и рассчитать только 4 * угол + 4 * средний край + 1 * средний, например ::10000 *
>>> patterns([], 6) == 4*patterns([1], 5) + 4*patterns([2], 5) + patterns([5], 5)
True