1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
from enigma import grid_adjacency, arg, printf # consider an n x n grid n = arg(3, 0, int) # adjacency matrix adj = grid_adjacency(n, n, include_diagonal=1) # generate paths with k additional steps, prefix p, visiting different squares def paths(k, p): # are we done? if k == 0: yield p else: # extend the path for x in adj[p[-1]]: if x not in p: yield from paths(k - 1, p + [x]) # count maximal length paths that start at square 0 k = n * n - 1 t = sum(1 for p in paths(k, [0])) printf("total paths = {t}") |

The code can be executed on repl.it [ https://repl.it/@jim_r/teaser2905 ].

From square 0 we can go to to the central square (4) or to an edge square (1 or 3), so we can just count the paths with prefix [0, 4] and [0, 1]. There will be the same number of paths with prefix [0, 3] as there are with prefix [0, 1].

1 2 3 4 |
>>> sum(1 for p in paths(7, [0, 4])) + 2 * sum(1 for p in paths(7, [0, 1])) 138 |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
# use a dictionary to map the connections between the letters graph = { 'E':'TFI', 'T':'EHFIG', 'H':'TIG', 'F':'ETIOL', 'I':'ETHFGOLD', 'G':'THILD', 'O':'FIL', 'L':'FIGOD', 'D':'IGL' } # find paths visiting all nodes in the graph <graph>, each # only once def find_path(graph, path): # have all nodes been visited if len(path) == 9: yield path else: # consider possible next nodes for n in graph[path[-1]]: # ... if they are not already in the path if n not in path: # proceed to the next node yield from find_path(graph, path + n) pths = tuple(find_path(graph, 'E')) print(f'There are {len(pths)} routes:', end='') for i, p in enumerate(pths): if not i % 6: print() print(p, end=' ') print() |

Erling Torkildsen provides a GeoGebra model for this teaser here.

]]>