From The Sunday Times, 23rd December 2018 [link]
In this Teaser, a jig* is defined as an outwards move to an adjacent empty square, either horizontally, upwards or downwards, the letter * being inserted in all such squares.
Begin with the letter W on a regular grid of empty squares.
From the W, jigO. From every O, jigN. From every N, jigD, and so on until the central diagonal reads SELIM’S TIRED, NO WONDER, IT’S MILES.
Looking at your grid of letters, in how many ways can you trace the palindrome above?
[You can start at any S, move to adjacent letters till you reach the W and then on to any S (including the one you started at). You may move up and down, left and right.]
[teaser2935]
Enigmatic Code 
Here’s a constructive solution that makes the grid and then uses generic path counting code to count the number of possible paths.
It runs in 78ms, so I didn’t think it was necessary to exploit the symmetry in the puzzle to get a faster solution.
Run: [ @repl.it ]
from enigma import irange, divf, grid_adjacency, cached, printf # the palindrome p = "SELIMSTIREDNOWONDERITSMILES" n = len(p) n2 = n * n # construct the grid g = ['.'] * n2 # index (r, c) into the grid fn = lambda r, c: r * n + c # fill out the grid m = divf(n, 2) for r in irange(0, m): s = p[:r] + p[r::-1] for (i, x) in enumerate(s): c = m - r + i g[fn(r, c)] = x if r != m: g[fn(n - r - 1, c)] = x # output the grid #from enigma import chunk, join #for r in chunk(g, n): print(join(r, sep=' ')) # now count the paths on the grid # (this is generic path counting code) # adjacency matrix adj = grid_adjacency(n, n) # count paths from i with k letters (of p) remaining @cached def npaths(k, i): return (1 if k == 0 else sum(npaths(k - 1, j) for j in adj[i] if g[j] == p[-k])) # start with p[0] t = 0 for (i, x) in enumerate(g): if x != p[0]: continue k = npaths(n - 1, i) t += k printf("[i={i} k={k} t={t}]") printf("total paths = {t}")Solution: There are 1,073,479,696 different ways of tracing the palindrome.
With a bit of analysis we can exploit the symmetry of the palindrome as well as the 4-fold symmetry of the grid to get a solution with less computation, although there is only a slight improvement in execution time.
And with a complete analysis we can get the solution down to a single expression:
Here is my complete analysis:
Ignoring all non-letters, the completed grid looks like this:
When tracing the palindrome we first note that the S’s that are not on the perimeter of the square cannot be starting points (as they are never next to an E).
There is only one W, so all paths must go S … W (in the centre) and then W … S. So the return path is just the reverse of some outward path. So if we knew how many paths from S … W there were, we can square it to get the total number of paths that trace the complete palindrome.
Now, if we start at the S in the top row, and make a path to W, at each square we can only choose to go to the square below. There is only one path. C(13, 13) = 1.
If we start at the first S on the second row, as we get towards the W in the middle we make 12 steps down and 1 step across (at some point), and we can choose at which point we make the step across. So there are C(13, 12) = 13 paths.
If we keep considering the first S on the third row, we get one more choice for the step across, so we get C(13, 11) paths, and then C(13, 10), C(13, 9), …. paths for each starting point.
So we end up with the following expression as the number of paths starting along the top left line of S’s:
This is the number of subsets of size 1 to 13 of a set of size 13, so we can write this expression as:
(Another way to see this is, if we start from the W in the centre and only make moves upwards and leftwards we end up, after 13 choices at one of the S’s on the top-left diagonal edge of the square. So there are 2^13 possible paths, but we want to exclude the path that goes to the leftmost S (in the 1st column), so there are only (2^13 − 1) paths that we are interested in).
But there are 4 lines of S’s, the number of possible paths from S … W is:
Now, if we then consider the return paths, we can square this to get the total number of possible ways to trace the palindrome, giving: