4
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think I'm missing something. I did what you suggested for the first case I provided (A4 to C4) and came up with N = 2. I came up with the following for numbers, $dist = 2, D_{min} = 0, S = 1, M = 0$ $\endgroup$ – shellhead Feb 14 '15 at 21:51
  • $\begingroup$ There, there are more substitutions because the two points are already colinear. So, there are other substitutions you could make. 2 diagonals on the left, 2 diagonals on the right, or 2 verticals straight up. $\endgroup$ – Axoren Feb 14 '15 at 23:24
  • $\begingroup$ @shellhead In the corrected equation, that back diagonal is accounted for naturally. $\endgroup$ – Axoren Feb 14 '15 at 23:44
  • $\begingroup$ I think the substitutions have been massively undercounted. If you have a vertical stretch of length 4, then you not only have the option of some 2-edge zigzags, but you can also do a big "v": NW, NW, NE, NE or vice versa. And the number of substitutions depends on whether your vertical stretch is in the middle or at the edge of the board. $\endgroup$ – Tad Feb 15 '15 at 15:02
  • $\begingroup$ @Tad, that's counted by the fact that the pieces of the substitution can happen in any order. In fact, all of these moves can happen in any order, as long as they're all present. A large V-shape would be "back, back, back, forward, forward, forward", but that's just a reordering of "back, forward, back, forward, back, forward", which is taken into consideration by the multinomial. $\endgroup$ – Axoren Feb 15 '15 at 19:34
2
$\begingroup$

Commenting here because of low rep:

I think the current solution is almost correct except that it is treating A4-B5-C4 and A4-B3-C4 as the same path because they are both made up of two diagonal elements. Someone should verify but I believe the correct equation is,

$N = \sum_{s=0}^{S}\binom{dist}{D_{min}+s,s,2(S-s)+M}$

For your specific example, in the final summation,

$N = \sum_{s=0}^{S}\binom{dist}{D_{min}+s,s,2(S-s)+M}= \sum_{s=0}^{1}\binom{dist}{s,s,2-2s}=\binom{dist}{0,0,2}+\binom{dist}{1,1,0}=1+2=3$

$\endgroup$
  • 1
    $\begingroup$ The intuition is as follows. We know the distance and the number of minimum diagonal moves. Given $s$, the number of substitutions, the number of extra diagonal moves in the original diagonal direction is $s$. There will be either be $2(S-s)+M$ horizontal or vertical moves. Each path is constructed by choosing $D_{min}+s$ moves to go in diagonal direction 1 and $2(S-s)+M$ moves in the horizontal or vertical direction. The remaining moves must be diagonal direction 2. $\endgroup$ – alw Feb 14 '15 at 23:36
  • $\begingroup$ Although this does work for the example given, we do need to separate the straight and back moves because of the definition of the multinomial. They need to add up to $dist$. Thanks for catching the error. $\endgroup$ – Axoren Feb 14 '15 at 23:40
1
$\begingroup$

An experimental approach: for the special case where the starting point is in the corner of the board, I generated the terms by dynamic programming and found the two-dimensional array in OEIS. There doesn't appear to be a simple formula, but it's easy to see via the calculus of finite differences that the entries in the $d$-th off-diagonal are given by a degree-$d$ polynomial.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.