I'm struggling to come up with an equation that can determine the number of shortest paths for a King between two points on a chess board. I came across Getting the shortest paths for chess pieces on n*m board, which uses a BFS to find the answer. However, I don't really need to know the path and I was hoping to come up with a general equation. I also noticed this was similar to some questions asked about finding Lattice Paths, however in this case, the path may contain horizontal movement.
I started with a small case, with the starting point of A4 and a target point of C4. It's quick to see there are only three shortest paths between the two points (A4-B5-C4, A4-B4-C4, and A4-B3-C4).
Then I expanded, starting out at A4 and targeting D4 and came up with seven possible shortest paths (A4-B5-C5-D4, A4-B5-C4-D4, A4-B4-C5-D4, A4-B4-C4-D4, A4-B3-C3-D4, A4-B3-C4-D4, A4-B4-C3-D4).
At this point it seemed like coming up with an equation wouldn't too terribly hard, but my math skills fail me here. Starting with the first case (A4-C4), from the starting location, A4, it seems there are three possible choices. Then from any of those spaces, there is only one possible choice, C4.
For the second case (A4-D4), from the start there are again only three possible choices. Then from those three locations, two only have two choices (B3 & C5) and one has three choices (C4). Then, from all of those resulting locations, there is only once choice, D4.
I feel like I'm close, but cannot solidify an equation. Any help would be greatly appreciated.
Best Answer
Assuming you're not including obstacles, the shortest distance is:
$$dist = \max(\text{horizontal distance}, \text{vertical distance})$$
This is because the most distance is covered to a destination by going diagonally. So, the king moves diagonally as much as possible before it would put them past the row or file the target square is on. Then, the king moves toward the square along that row or file. This is the shortest distance, so all shortest paths have this distance.
A shortest path cannot consist of a horizontal move and a vertical move, otherwise there is a shorter path consisting of one less move in which it used a diagonal move instead.
A shortest path will only have a horizontal move or a vertical move if the horizontal distance is not equal to the vertical distance.
A shortest path has a minimum number of diagonal moves $D$ equal to:
$$D_{min} = \min(\text{horizontal distance}, \text{vertical distance})$$
Two vertical moves can be substituted with two diagonal moves instead (zig-zagging out-and-into the file). The same can be done for two horizontal moves. The number of such substitutions $S$ is equal to:
$$S = \left\lfloor{\frac{dist - D_{min}}{2}}\right\rfloor$$
There are a number of mandatory unsubstituteable vertical or horizontal moves $M$ equal to (0 or 1):
$$M = dist - D_{min} - 2S$$
So, there are $S$ substitutions to make $S+1$ if we count no substitutions, which we will. We can make $0, 1, 2, ... S$ substitutions. With this, we have enough to decide how many paths there are.
$$ N = \sum_{s = 0}^S \binom{dist}{D_{min}+s, 2S - 2s + M, s} = \sum_{s = 0}^S \frac{dist!}{(D_{min}+s)!(2S - 2s + M)! s!}$$
Edit: There was a mistake in the formula. For better understanding of the formula in case there's still a mistake: $$\binom{dist}{\text{forward diagonals, straight moves, back diagonals}}$$
You have to sum over every possible combination of substitutions at the end.