Enigmatic Code

Programming Enigma Puzzles

Grid puzzle

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?

5 responses to “Grid puzzle

  1. Jim Randell 27 June 2018 at 8:03 am

    There’s a handy [[ grid_adjacency() ]] function in the enigma.py library to compute the adjacency matrix on a grid of squares.

    The following Python program constructs the paths on an m×n grid, and counts them. It can be used, for example, to solve Sunday Times Teaser 2905 (using a 3×3 grid). But as m and n increase 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.

    from enigma import grid_adjacency, icount, arg, printf
    
    # consider an m x n grid
    m = arg(2, 0, int)
    n = arg(m, 1, int)
    
    # adjacency matrix
    adj = grid_adjacency(m, 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
    printf("[{m}x{n} grid]")
    k = m * n - 1
    t = icount(paths(k, [0]))
    printf("paths = {t}")
    

    So, instead of constructively counting paths on the 2×k grid I looked at an analytical way of determining the number of paths.

    I started by considering the paths on an 2×k grid, 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 number R(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–1 steps towards the right hand end, we have a choice of staying on the row we are on, or switching rows.

    R(k) = 2^(k – 1)

    We can then move on to considering the number of paths on a 2×k grid 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 number P(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 are P(k – 1) paths that start with (1, 2, 3), and another P(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 are P(k – 2) paths starting with (1, 3, 2, 4, 5) and another P(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 are R(k – 2) paths that start with (1, 3, 5). Similarly there are R(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 another P(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 are R(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×k grid.

    Adding them all up we get the following recurrence relation:

    P(k) = 2.P(k – 1) + 2.P(k – 2) + 2.R(k – 2) + 2.P(k – 2) + 2.R(k – 2)
    P(k) = 2.P(k – 1) + 4.P(k – 2) + 4.R(k – 2)

    and we already know:

    P(1) = 1
    P(2) = 6

    and given we have a closed form for R(k) = 2^(k – 1), we can simplify this to:

    P(1) = 1
    P(2) = 6
    P(k) = 2.P(k – 1) + 4.P(k – 2) + 2^(k – 1)

    (If we use a similar approach to find a recurrence relation for R(k), we get:

    R(1) = 1
    R(k) = 2.R(k – 1)

    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..20 takes less than 1ms.

    Run: [ @repl.it ]

    from enigma import arg, printf
    
    # generate successive P(k) terms starting with P(1)
    # using the recurrence relation
    def generate():
      (a, b, c) = (1, 6, 4)
      yield a
      while True:
        yield b
        (a, b, c) = (b, 2 * b + 4 * a + c, 2 * c)
    
    # find the first n terms
    n = arg(20, 0, int)
    for (i, p) in enumerate(generate(), start=1):
      printf("P({i}) = {p}")
      if i == n: break
    

    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) for k=1..20:

    P(1) = 1
    P(2) = 6
    P(3) = 20
    P(4) = 72
    P(5) = 240
    P(6) = 800
    P(7) = 2624
    P(8) = 8576
    P(9) = 27904
    P(10) = 90624
    P(11) = 293888
    P(12) = 952320
    P(13) = 3084288
    P(14) = 9986048
    P(15) = 32325632
    P(16) = 104628224
    P(17) = 338624512
    P(18) = 1095892992
    P(19) = 3546546176
    P(20) = 11477188608

    Some closed forms for P(k):

    P\left( k \right)\; =\; \frac{1}{10}\left[ \left( 5\; +\; \sqrt{5} \right)\left( 1\; +\; \sqrt{5} \right)^{k}\; +\; \left( 5\; -\; \sqrt{5} \right)\left( 1\; -\; \sqrt{5} \right)^{k} \right]\; -\; 2^{k\; -\; 1}

    P\left( k \right)\; =\; \frac{1}{2\sqrt{5}}\left[ \left( 1\; +\; \sqrt{5} \right)^{k\; +\; 1}\; -\; \left( 1\; -\; \sqrt{5} \right)^{k\; +\; 1} \right]\; -\; 2^{k\; -\; 1}

    Note that SymPy can be used to solve recurrence relations. For example: [link].

    • Hugh Casement 27 June 2018 at 11:30 am

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

      • Jim Randell 27 June 2018 at 11:48 am

        Using Hugh’s suggestion, we can separate the powers of 2 in the calculation of P(k), to note that P is the pairwise product of:

        (1, 2, 4, 8, 16, 32, 64, 128, …) and (1, 3, 5, 9, 15, 25, 41, 67, …)

        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:

        def generate():
          (a, b, c) = (1, 3, 2)
          yield a
          while True:
            yield b * c
            (a, b, c) = (b, a + b + 1, 2 * c)
        
  2. paul2cleary 27 June 2018 at 2:51 pm

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

  3. Jim Randell 28 June 2018 at 11:08 am

    The [[ fib() ]] function in the enigma.py library can be used to generate Fibonacci sequences, where each term is the sum of the previous k terms. 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.

    from enigma import fib, unpack, arg, printf
    
    # a sequence that doubles, starting from 4
    D = fib(4, fn=unpack(lambda x: 2 * x))
    
    # number of paths on a 2*k grid
    P = fib(1, 6, fn=unpack(lambda a, b: 4 * a + 2 * b + next(D)))
    
    # output the first n terms
    n = arg(20, 0, int)
    for (i, p) in enumerate(P, start=1):
      printf("P({i}) = {p}")
      if i == n: break
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: