Shortest path for a knight

Question

Is there a practical way of computing the shortest path from a square to another, for a knight? (for a human chess player, not for a computer)

Usually, when I want to send my knight from a square to another, I try to find a path with a rather empirical way. "OK, to get there, I should go here or here... But this square is attacked, so I can only go here..." and so on. Is there a more straightforward approach?

Thanks in advance.

Answer 1

To me the easy human way it is to start from the square that you want to go to (backtracking approach), lets call it 'A' and exclude from the path calculation the direct linked paths from 'A' that you can't go to because they are attack or there is a piece on it.

For example, you want to go to the square c4, so the directed linked paths will be from by a5, a3, b2, d2, e3, e5, d6 and b6, but if only the square a5 and b6 are available you can reduce your calculation to only to 2 paths now. Furthermore, if you use this "technique" you can check if the target square is reachable at all (if have at least 1 directed linked path not being occupied or attacked).

After doing that, you go to the position where you knight stands and you check which are the squares that you can go to. Using this two phase approach you reduce you tree of calculation immensely.

You should also know beforehand how many moves you need to go from one square to another with your knight, in order to avoid the calculation of larger paths than the ones really need it. I din't check online to find any heuristic for this but I can give you some inside tips about it:

• The Knight on a black square can only go to a white square and vise-versa, in the next move;
• Every square on the diagonal of the actual square of the Knight can be reach in only two moves. Square (x,y) to the squares (x-1,y+1), (x+1,y+1), (x+1,y-1) and (x-1,y-1) takes 2 moves;
• The squares up, above, right and left of the actual square takes 3 moves;
• Every square on the diagonal of the actual square with a one square between them (e.g actual square = c4, target square a6), takes 4 moves.
• Every square on the diagonal of the actual square with a 2 squares between them (e.g actual square = c4, target square f7), takes only 2 moves.

Finally, if you are in a given color square you will take a odd number of moves to reach the opposite color square. If the target square have the same color as the square that you are in now it will take a even number of moves.

Answer 2

It's well documented.

It's actually a fairly boring metric. The only special cases are the squares next to the knight and the squares on the same diagonal that are two squares away. In all other cases, quite regular.

If you mean with other pieces on the board, you get a shortest path problem which is related to the Travelling Salesman Problem but is soluble in polynomial time.

Answer 3

I know this is a super old question. I made a program that outputs all the positions a knight can be relative to starting position within six moves(which happens to be the maximum number of moves needed to get anywhere)

0: (0, 0) 
1: (2, 1) 
2: (2, 0) (3, 3) (4, 2) (3, 1) (1, 1) (4, 0) 
3: (3, 2) (5, 4) (4, 1) (3, 0) (6, 1) (6, 3) (4, 3) (5, 0) (1, 0) (5, 2) 
4: (7, 3) (6, 4) (5, 5) (6, 6) (7, 1) (4, 4) (6, 0) (6, 2) (7, 5) (2, 2) (5, 1) (5, 3) 
5: (7, 4) (6, 5) (7, 0) (7, 6) (7, 2) 
6: (7, 7)

Number on the left is turn number, and the list on the right corresponds to all the positions the knight can be in with duplicate positions removed (we don't care that you can go back to your starting position for example, these are the shortest paths to each of these positions). Also, no negative numbers are represented. For example 2,1 -2,1, 2,-1 and -2,-1 are all considered the same position. Also the biggest number is always shown first. For example (4,2) means the night can move 4 spaces in some direction, and then 2 in an orthogonal direction.

One more caveat is that these numbers are the theoretical minimum with no pieces in the way, and a theoretical infinite plane to work with. That is, to achieve this could potentially require moves that exit the game board and come back. I think it only requires exiting in rare cases. For example, if you're in a corner of a board and want to move 1,1 toward the center, the 2 moves that should be able to do this require you going out of bounds first.

Memorizing this is probably not that useful, but there's some interesting takeaways that may be worth noting.

For example, it takes a whole 3 moves to move a knight 1 square forward.