Sunday Times Teaser 2905 – Trackword

by Danny Roth

Published May 27 2018 (link)

George and Martha are tackling a Trackword problem which appears in magazines. Nine letters are placed in a 3×3 grid and you have to work from one square to a neighbour, proceeding up, down, left, right or diagonally until all nine squares have been visited to form a nine-letter word. You must start in the top-left corner. As an example, you can get the word EIGHTFOLD from the following grid:

E	T	H
F	I	G
O	L	D

George and Martha thought that would be interesting to work out how many possible routes there are which start in the top-left corner.

How many routes are there?

2 Comments Leave one →

Brian Gladman permalink


# 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()

# 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.

Jim Randell permalink

There’s a handy grid_adjacency() function in the enigma.py library [ https://www.magwag.plus.com/jim/enigma.html ] to compute the adjacency matrix on a square grid.


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}")

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].


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

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

138

Sunday Times Teaser 2905 – Trackword

by Danny Roth

Published May 27 2018 (link)

Leave a comment to Jim Randell Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta