Knight in n, part 1: moves

Consider the following problem:

A knight is placed at the origin of a chessboard that is infinite in all directions. How many ways are there for that knight to reach cell (i,j) in exactly n moves?

This knight moves problem is not hard, nor does it have any real life applications. The problem is still interesting because there are many different ways to solve it, ranging from very simple to quite complex. In this series of articles I will describe some of these solutions.

Knight's moves

The possible moves for a chess knight

In chess, a knight can move two squares horizontally and one square vertically, or two squares vertically and one square horizontally. One complete move therefore looks like the letter 'L'. The picture on the right shows all possible moves for the black knight in the center.

We can summarize all these moves in an array:

moves :: [(Int,Int)]
moves = [(2,1),(2,-1),(-2,1),(-2,-1)
        ,(1,2),(-1,2),(1,-2),(-1,-2)]

Counting the number of paths to (i,j) in n steps can now be done with a simple recursive function. The base case is that in 0 moves only cell (0,0) is reachable. In the recursion step we simply try all moves:

pathsrec :: Int -> (Int,Int) -> Integer
pathsrec 0 (0,0) = 1
pathsrec 0 (_,_) = 0
pathsrec n (i,j) = sum [ pathsrec (n-1) (i+δi,j+δj) | (δi,δj) <- moves ]

So for example

Knight1> paths_rec 4 (2,2)
54

I.e. there are 54 ways to reach cell (2,2) in 4 moves.

Unfortunately the function pathsrec is not very efficient. In fact, it is very much not efficient. At each step all 8 possible moves are considered, so the total time complexity of this function is O(8n).

Tables

Besides calculating the number of paths to a single point it can also be interesting to display the number of pats for each possible end point. We can make a list of lists containing all the path counts,

pathMatrix paths n
    = [ [ paths n (i,j) | j <- [-2*n .. 2*n] ] | i <- [-2*n .. 2*n] ]

and then display this list in a tabular format

showMatrix :: Show α => [[α]] -> String
showMatrix xss = unlines [ unwords [ show x | x <- xs ] | xs <- xss ]
printPathMatrix paths = putStr . showMatrix . pathMatrix paths

The path matrix for n=1 should be familiar, it is the same as the image of possible moves of a knight.

Knight1> printPathMatrix pathsrec 1
    0 1 0 1 0
    1 0 0 0 1
    0 0 0 0 0
    1 0 0 0 1
    0 1 0 1 0

But now we can also make larger tables:

Knight1> printPathMatrix pathsrec 2
    0 0 1 0 2 0 1 0 0
    0 2 0 2 0 2 0 2 0
    1 0 0 0 2 0 0 0 1
    0 2 0 2 0 2 0 2 0
    2 0 2 0 8 0 2 0 2
    0 2 0 2 0 2 0 2 0
    1 0 0 0 2 0 0 0 1
    0 2 0 2 0 2 0 2 0
    0 0 1 0 2 0 1 0 0

If you were to continue increasing n, the table and the numbers in it become ever larger. It is a good idea to make a 'density plot', i.e. to use colors to visualize larger numbers. For example for n=4, the path matrix can be rendered as:

Special cases

Looking at the above matrices, you might start to see some patterns emerge:

These observations can be used as additional cases in the recursive function to quickly eliminate large parts of the input space:

pathscase :: Int -> (Int,Int) -> Integer
pathscase 0 (0,0) = 1
pathscase 0 (_,_) = 0
pathscase n (i,j) | (n+i+j) `mod` 2 /= 0 = 0
pathscase n (i,j) | abs i + abs j > 3*n  = 0
pathscase n (i,j) | abs i > 2*n          = 0
pathscase n (i,j) | abs j > 2*n          = 0
pathscase n (i,j) = sum [ pathscase (n-1) (i+δi,j+δj) | (δi,δj) <- moves ]

A quick test shows that this can be a big improvement for the run time:

Knight1> pathsrec 8 (4,4)
124166
(92.88 secs, 4605991724 bytes)
Knight1> pathscase 8 (4,4)
124166
(17.69 secs, 807191624 bytes)

The asymptotic time complexity of pathscase is harder to analyze. It is still O(8n) in the worst case, but the complexity is now also output dependant.


That is all for now, next time we will look at smarter algorithms. For the interested reader I would suggest that you try to come up with some ideas of your own. I would love to hear how other people approach this problem.

Comments

I'd go repeatedly folding the move matrix (paths_srec 1) onto itself for the wanted number of steps. That is much more efficient than computing each element separately (about O(n^3)?).

Or do some memoizing. :-)

Folding is basically the dynamic programming solution to this problem, and it should indeed give an O(n^3) solution. Memoization is equivalent to dynamic programming, you are just doing the operations in a different order.

This is only part 1 of the series on this problem, I plan to treat this solution in part 3.

Reply

(optional)
(optional, will not be revealed)
Name a function of type (a -> b) -> ([a] -> [b]):
Use > code for code blocks, @code@ for inline code. Some html is also allowed.