A Symmetric Approach to the Knight Puzzle

2024 Aug 30

Professor Alex Biryukov recently asked me the following question:

Consider an n-by-n square checkerboard where the Knight is in the middle. Compute the number of unique paths that the Knight can take in T steps without ever leaving the board.

Consider n = 5 as an example. 

One straightforward approach is to use dynamic programming. The following is a code snippet in Python.

knightMoves = [[-1, -2], [-2, -1], [-1, +2], [-2, +1], [+1, -2], [+2, -1], [+1, +2], [+2, +1]] # How knight moves around the checkerboard

n = 5 # The dimension of the checkerboard

# tab = [[2,3,4,3,2],[3,4,6,4,3],[4,6,8,6,4],[3,4,6,4,3],[2,3,4,3,2]] for n = 5

T = 100 # The number of steps the knight takes

def computePaths(n, curLocation, numSteps):

   dp = [[[0 for step in range(n)] for x in range(n)] for y in range(numSteps + 1)]

   # Start from the initial point

   dp[0][curLocation[0]][curLocation[1]] = 1

   # Fill dp table

   for step in range(1, numSteps + 1):

       for x in range(n):

           for y in range(n):

               for move in knightMoves:

                   stepx = x + move[0]

                   stepy = y + move[1]

                   if 0 <= stepx < n and 0 <= stepy < n: # moves are reversible

                       dp[step][x][y] += dp[step-1][stepx][stepy]

   # Sum over DP table

   pathCount = 0

   for x in range(n):

       for y in range(n):

           pathCount += dp[numSteps][x][y]  

   return pathCount

pathCount = computePaths(n, [2,2], T)

Another approach is to make use of the symmetry of the board on top of Markov decision process. We first compute the number of next steps that each square can take. We then color the squares according to their next step configuration, i.e.,  the number and colors of squares that a square can transit into. 

We can then draw the transition graph and write down the transition matrix. 

Denote the transition matrix as A, i.e., A = [a b c d e]

A = 0 1 0 0 0

8 0 2 0 0

0 2 0 4 0

0 0 2 0 2

0 0 0 2 0

Initial position at the center (represented corresponding to the arrangement of A):

x = [1 0 0 0 0]

We can then compute the number of paths after T steps as Sum(x * (A^T)). 

The following are a few outputs of this method, and they are consistent with the outputs of the DP program.

Number of steps T Sum(x * (A^T))

1 8

10 2807808

20 4832473645056

30 8293608608369737728

99 85718379387099805918515221988077997026934633227442955546001408

100 363672284021636688954470859598443930455076334186446217386393600