Graph algorithm involving chess: possible paths in k moves

Question

I'm trying to solve an algorithm problem involving chess.

Suppose I have a king in A8 and want to move it to H1 (only with allowed moves). How could I find out how many possibilities (paths) there is making exactly any given k moves? (e.g. How many paths/possibilities there is if I want to move the king from A8 to H1 with 15 moves?)

One trivial solution is to see it as a graph problem and use any standard path finding algorithm counting each move as having cost 1. So, let's say I want to move my king from A8 to H1 in 10 moves. I would simply search all paths which sum up to 10.

My question is, if there are other more clever and efficient ways of doing this? I was also wondering, if there could be something more "mathematical" and straightforward to find this number and not so "algorithmic" and "brute-force-like"?

Answer 1

This is a straight-forward O(N^3) dynamic programming problem.

Simply assign a 3D array as follows:

Let Z[x][y][k] be the number of moves of k steps to reach the destination from position (x,y) on board.

The base cases are:

foreach x in 0 to 7,
   foreach y in 0 to 7,
       Z[x][y][0] = 0 // forall x,y: 0 ways to reach H1 from
                      // anywhere else with 0 steps

Z[7][7][0] = 1 // 1 way to reach H1 from H1 with 0 steps

The recursive case is:

foreach k in 1 to K,
   foreach x in 0 to 7,
      foreach y in 0 to 7,
          Z[x][y][k+1] = Z[x-1][y][k]
              + Z[x+1][y][k]
              + Z[x][y-1][k]
              + Z[x][y+1][k]
              + ...; // only include positions in
                     // the summation that are on the board
                     // and that a king can make

Your answer is then:

return Z[0][0][K]; // number of ways to reach H1(7,7) from A8(0,0) with K moves

(There is a faster way to do this in O(n^2) by decomposing the moves into two sets of horizontal and vertical moves and then combining these and multiplying by the number of interleavings.)

See this related question and answer: No of ways to walk M steps in a grid