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

.......E <-end
........
........
........
........
........
........
S....... <-start

Unfortunately you can't use "any standard path finding algorithm" because your paths might not be shortest-paths. You'd have to specifically use a naive search which considered all paths (depth-first or breadth-first, for example).

However, because you don't care how you got to a tile, you can use a technique called dynamic programming. For every location (i,j), the number of ways to get there in n moves (let's call it ways_i,j(n)) is:

ways_i,j(n) = ways_i-1,j(n-1) + ways_i+1,j(n-1) + ways_i,j-1(n-1) + ways_i,j+1(n-1) + ways_i+1,j+1(n-1) + ways_i-1,j+1(n-1) + ways_i+1,j-1(n-1) + ways_i-1,j-1(n-1)

That is, the king can move from any of the adjacent squares in 1 move:

ways_i,j(n) = sum_{neighbors(i,j)}(ways_neighbor(n-1))

Thus you'd do, for example in python:

SIZE = 8

cache = {}
def ways(pos, n):
    r,c = pos  # row,column
    if not (0<=r<SIZE and 0<=c<SIZE):
        # off edge of board: no ways to get here
        return 0
    elif n==0:
        # starting position: only one way to get here
        return 1 if (r,c)==(0,0) else 0
    else:
        args = (pos,n)
        if not args in cache:
            cache[args] = ways((r-1,c), n-1) + ways((r+1,c), n-1) + ways((r,c-1), n-1) + ways((r,c+1), n-1) + ways((r-1,c-1), n-1) + ways((r+1,c-1), n-1) + ways((r+1,c-1), n-1) + ways((r+1,c+1), n-1)
        return cache[args]

Demo:

>>> ways((7,7), 15)
1074445298

The above technique is called memoization, and is simpler to write than dynamic programming, because you don't need to really think about the order in which you do things. You can see the cache grow as we perform a series of larger and larger queries:

>>> cache
{}
>>> ways((1,0), 1)
1
>>> cache
{((1, 0), 1): 1}
>>> ways((1,1), 2)
2
>>> cache
{((0, 1), 1): 1, ((1, 2), 1): 0, ((1, 0), 1): 1, ((0, 0), 1): 0, ((2, 0), 1): 0, ((2, 1), 1): 0, ((1, 1), 2): 2, ((2, 2), 1): 0}
>>> ways((2,1), 3)
5
>>> cache
{((1, 2), 1): 0, ((2, 3), 1): 0, ((2, 0), 2): 1, ((1, 1), 1): 1, ((3, 1), 1): 0, ((4, 0), 1): 0, ((1, 0), 1): 1, ((3, 0), 1): 0, ((0, 0), 1): 0, ((2, 0), 1): 0, ((2, 1), 1): 0, ((4, 1), 1): 0, ((2, 2), 2): 1, ((3, 3), 1): 0, ((0, 1), 1): 1, ((3, 0), 2): 0, ((3, 2), 2): 0, ((3, 2), 1): 0, ((1, 0), 2): 1, ((4, 2), 1): 0, ((4, 3), 1): 0, ((3, 1), 2): 0, ((1, 1), 2): 2, ((2, 2), 1): 0, ((2, 1), 3): 5}

(In python, can also use a @cached or @memoized decorator to avoid having to write the entire code in the last else: block. Other languages have other ways to automatically perform memoization.)

The above was a top-down approach. It can sometimes produce very large stacks (your stack will grow with n). If you want to be super-efficient to avoid unnecessary work, you can do a bottom-up approach, where you simulate all positions the king could be, for 1 step, 2 steps, 3 steps, ...:

SIZE = 8
def ways(n):
    grid = [[0 for row in range(8)] for col in range(8)]
    grid[0][0] = 1

    def inGrid(r,c):            
        return all(0<=coord<SIZE for coord in (r,c))
    def adjacentSum(pos, grid):
        r,c = pos
        total = 0
        for neighbor in [(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)]:
            delta_r,delta_c = neighbor
            (r2,c2) = (r+delta_r,c+delta_c)
            if inGrid(r2,c2):
                total += grid[r2][c2]
        return total

    for _ in range(n):
        grid = [[adjacentSum((r,c), grid) for r in range(8)] for c in range(8)]
        # careful: grid must be replaced atomically, not element-by-element

    from pprint import pprint
    pprint(grid)
    return grid

Demo:

>>> ways(0)
[[1, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0]]

>>> ways(1)
[[0, 1, 0, 0, 0, 0, 0, 0],
 [1, 1, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0]]

>>> ways(2)
[[3, 2, 2, 0, 0, 0, 0, 0],
 [2, 2, 2, 0, 0, 0, 0, 0],
 [2, 2, 1, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0]]

>>> ways(3)
[[6,  11, 6, 4, 0, 0, 0, 0],
 [11, 16, 9, 5, 0, 0, 0, 0],
 [6,  9,  6, 3, 0, 0, 0, 0],
 [4,  5,  3, 1, 0, 0, 0, 0],
 [0,  0,  0, 0, 0, 0, 0, 0],
 [0,  0,  0, 0, 0, 0, 0, 0],
 [0,  0,  0, 0, 0, 0, 0, 0],
 [0,  0,  0, 0, 0, 0, 0, 0]]

>>> ways(4)
[[38, 48, 45, 20, 9,  0, 0, 0],
 [48, 64, 60, 28, 12, 0, 0, 0],
 [45, 60, 51, 24, 9,  0, 0, 0],
 [20, 28, 24, 12, 4,  0, 0, 0],
 [9,  12, 9,  4,  1,  0, 0, 0],
 [0,  0,  0,  0,  0,  0, 0, 0],
 [0,  0,  0,  0,  0,  0, 0, 0],
 [0,  0,  0,  0,  0,  0, 0, 0]]

Answer 2

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

Answer 3

You could use an adjacency matrix. If you multiply such a matrix with itself, you get the amount of paths from Point to Point. Example:

Graph: complete K3 graph : A<->B<->C<->A

Matrix:

[0 ; 1 ; 1]
[1 ; 0 ; 1]
[1 ; 1 ; 0]

Paths for length 2: M * M

[2 ; 1 ; 1]
[1 ; 2 ; 1]
[1 ; 1 ; 2]

Length 3 would then be M * M * M

[2 ; 3 ; 3]
[3 ; 2 ; 3]
[3 ; 3 ; 2]