Search code examples
algorithmgraph-algorithmchess

Graph algorithm involving chess: possible paths in k moves


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"?


Solution

  • 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