### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,367)
- misc (4)
- project euler (2)
- puzzle (90)
- puzzle# (48)
- site news (58)
- tantalizer (94)
- teaser (7)

### Site Stats

- 233,130 hits

Programming Enigma Puzzles

27 June 2018

Posted by on I drew a 2×2 grid with the numbers 1-4 in it, odd numbers on the top row, even numbers on the bottom row, as below:

Starting at 1 and moving to adjacent squares (diagonal moves are allowed). There are 6 paths that visit all the squares in the grid:

(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2).

I then extended my grid to 2×8 grid, as shown:

How many paths are there on the new grid? (Each path must start at 1, and by moving to adjacent squares visit every square in the grid exactly once).

And how many paths are there on a 2×20 grid?

%d bloggers like this:

There’s a handy [[

`grid_adjacency()`

]] function in theenigma.pylibrary to compute the adjacency matrix on a grid of squares.The following Python program constructs the paths on an

m×ngrid, and counts them. It can be used, for example, to solveSunday Times Teaser 2905(using a 3×3 grid). But asmandnincrease in size it begins to take a long time, so while it can be used to calculate the paths on the 2×8 grid (which takes about a second), it takes too long to calculate the paths on the 2×20 grid.So, instead of constructively counting paths on the 2×

kgrid I looked at an analytical way of determining the number of paths.I started by considering the paths on an 2×

kgrid, where we start at square 1 and finish at square 2 (the square below 1), visiting all the squares in the grid. We denote this numberR(k).One way to work this out is to consider that we must progress to the right hand end of the grid, and then return using the unused squares, so on each of the

k–1steps towards the right hand end, we have a choice of staying on the row we are on, or switching rows.We can then move on to considering the number of paths on a 2×

kgrid that start at square 1, and visit all the squares in the grid (but don’t have to finish at square 2). We denote this numberP(k).Starting at square 1 we have a choice of 3 onward squares: 2, 3 or 4.

If our second square is square 2, (so the path begins (1, 2)), then we have visited the leftmost column of the grid, and we have a choice of 2 onward squares (3 or 4), for each of these choices we need to find a path on the remaining

2×(k – 1)grid, starting from the a corner square and visiting every square on the remaining gird. So there areP(k – 1)paths that start with (1, 2, 3), and anotherP(k – 1)paths starting with (1, 2, 4).If our second square is square 3, (so the path begins (1, 3)), we can move on to squares 2, 4, 5 or 6. If we move on to square 2, then we must then choose square 4, and then have a choice of 2 onward squares (5 or 6), each of which requires finding a path on the remaining

2×(k – 2)grid. So there areP(k – 2)paths starting with (1, 3, 2, 4, 5) and anotherP(k – 2)paths starting with (1, 3, 2, 4, 6).If we start (1, 3, 4), then we can’t get back to collect square 2, so there will be no paths visiting every square that begin with this prefix.

If we start (1, 3, 5), then we will have to finish on square 2, and the penultimate square will have to be 4, but any path through the

2×(k – 2)grid starting on square 5 and finishing on square 6 will achieve this. So there areR(k – 2)paths that start with (1, 3, 5). Similarly there areR(k – 2)paths that start with (1, 3, 6).Finally if our second square is square 4, are onward choices are 2, 3, 5 or 6.

If we start (1, 4, 2) we must then go to 3, and then to 5 or 6. Giving

P(k – 2)paths starting (1, 4, 2, 3, 5) and anotherP(k – 2)paths starting (1, 4, 2, 3, 6).If we start (1, 4, 3), then we can’t get back to collect square 2, so there will be no paths visiting every square that begin with this prefix.

If we start (1, 4, 5), then the final square in the path must be 2, and the penultimate square 3, so we need a path on the

2×(k – 2)grid that starts at 5 and finishes at 6. So there areR(k – 2)paths starting with (1, 4, 5).Similarly, if we start (1, 4, 6) there are

R(k – 2)paths.And this is a full enumeration of the possible paths on the

2×kgrid.Adding them all up we get the following recurrence relation:

and we already know:

and given we have a closed form for

R(k) = 2^(k – 1), we can simplify this to:(If we use a similar approach to find a recurrence relation for

R(k), we get:The closed form of which is the formula given above).

Using this formula we can calculate

P(k)up to any desired amount.To calculate

k=1..20takes less than 1ms.Run:[ @repl.it ]Solution:On a 2×8 grid there are 8,576 paths. On a 2×20 grid there are 11,477,188,608 paths.Here are the values of

P(k)fork=1..20:Some closed forms for

P(k):Note that

SymPycan be used to solve recurrence relations. For example: [link].It’s not immediately obvious,

but the first part of that closed expression also has a factor 2^(k – 1).

Dividing, we are left with 2, 4, 6, 10, 16, 26, …

which is a modified Fibonacci sequence.

I don’t know whether that would allow us to derive a simpler closed expression,

P(k) = 2^(k – 1) times {Q(k) – 1}.

Using Hugh’s suggestion, we can separate the powers of 2 in the calculation of

P(k), to note thatPis the pairwise product of:where each element of the first sequence is twice the previous element, and each element of the second sequence is one more than the sum of the previous two elements.

This lets us implement a slightly simpler [[

`generate()`

]] function:(1,3,5,9,15,25,41,67) are (Fibonacci [n] – 1 + Lucas [n]).

The Linear recurrence of p(k) is {4, 0, -8}.

and a generating function of (1 + 2 x – 4 x^2) / (1 – 4 x + 8 x^3).

Lucas numbers are :- Ln = Ln – 1 + Ln – 2 with L1 = 1 and L2 = 3. The n-1 and n-2 are subscripts.

The [[

`fib()`

]] function in theenigma.pylibrary can be used to generate Fibonacci sequences, where each term is the sum of the previouskterms. But I’ve updated the code so a function can be provided that is used to generate the next term.We can use this to create a generator for

P.In case it’s of any interest,

http://discrete.openmathbooks.org/dmoi2/sec_recurrence.html

explains how to derive a closed expression for a recurrence relation

(at least the basic sort without an additional constant or a term such as R).

In this case 1 + √5 = 2φ and 1 – √5 = -2/φ are the roots of the characteristic equation x² – 2x – 4 = 0 corresponding to the recurrence relation for P (without the R term).

The factors are chosen to give the correct values for P1 and P2.