How many moves needed for a knight to go from any square to any other square?

Question

I want to find a sequence of knight moves that has a given origin and destination squares, preferably with the minimum number of moves. I can iterate over knight moves and collect visited squares, until I visit the destination square. I am asking how many iterations would I need to not miss an answer for any given pairs of squares.

I am trying to find the minimum number of iterations needed for looking at piece moves needed to reach from one square to a different square. I know bishops can't reach every square. I guess the knight is the slowest piece, except pawns, thus the title question is right to determine this problem. So I want an answer for every piece to reach every pair of squares.

Answer 1

You are asking for the diameter of the knight's graph. I suppose you only want it for the ordinary 8x8 chessboard. (See OEIS sequence A232007 for diameters of knight's graphs on square boards of size nxn, in particular confirming my answer 6 for the case n = 8. The answer is alleged to be ceiling(2n/3) for n > 4.)

The answer is 6. It takes 6 moves to get from a corner square to the opposite corner, say from a8 to h1.

There are many ways to get from a8 to h1 in 6 moves, e.g. a8-c7-e8-g7-h5-g3-h1.

To see that you can't get from a8 to h1 in less than 6 moves: First note that the Euclidean distance between a8 and h1 (measured from center to center and taking the side of a square as the unit of distance) is sqrt(7^2 + 7^2) = sqrt(98). The length of a single knight move is sqrt(2^2 + 1^2) = sqrt(5), so the maximum distance you can travel in 4 knight moves is 4 * sqrt(5) = sqrt(80) < sqrt(98), so a knight can't get from a8 to h1 in 4 moves or less. But it must take an even number of moves (since a8 and h1 have the same color), so at least 6 moves are needed.

Finally I have to show that you can get from any square to any other in at most 6 moves. This will take a bit of case work.

I. Starting from e4, you can reach any square in at most 3 moves, except the squares a8, c2, c6, g2, g6.

To see this, take an 8x8 grid and write 0 on the square e4. Next, write 1 on each square that can be reached by a knight's move from e4. Next, write 2 on each unmarked square within a knight's move of a square marked 1. Finally, write 3 on each remaining square which is a knight's move from a square marked 2. You will see that every square has been marked except for the five squares a8, c2, c6, g2, g6.

II. Therefore, a knight can get from any square to any other via e4 in at most 6 moves, unless at least one of the two squares is a8, c2, c6, g2, or g6.

III. By the same procedure as in step I, you can show that from c6 you can reach any square in at most 4 moves.

IV. From c2 (or g6) you can reach any square in at most 5 moves.

V. From g2 you can reach any square in at most 5 moves.

VI. From a8 you can reach any square in at most 6 moves.

Therefore, a knight can get from any square of the 8x8 chessboard to any other in a maximum of 6 moves (5 moves if the squares have opposite colors).

P.S. @Laska pointed out in a comment that this argument can be simplified:

I think the sufficiency argument can be simplified as the e4 statement also works for e5, d4 & d5. The tricky squares for e4 are those which are 2xsqrt(2) or 4xsqrt(2) away. No square is this distance from more than one of e4, e5, d4 & d5. So given any two squares there are at least two routes in 6 or less moves. They visit different squares in the centre 4: e4, e5, d4, d5. – Laska

Answer 2

The minimum number of knight moves required to be able to reach every square on the board, is 4 to 6, depending on which square you start from. Below is an overview; the number in each square indicates the minimum number of moves when starting from that square:

[6,5,5,5,5,5,5,6]
[5,5,5,4,4,5,5,5]
[5,5,4,4,4,4,5,5]
[5,4,4,4,4,4,4,5]
[5,4,4,4,4,4,4,5]
[5,5,4,4,4,4,5,5]
[5,5,5,4,4,5,5,5]
[6,5,5,5,5,5,5,6]

There are of course only 10 different sorts of squares, the rest of the board is these squares mirrored around a center line or a diagonal:

[6, , , , , , , ]
[5,5, , , , , , ]
[5,5,4, , , , , ]
[5,4,4,4, , , , ]
[ , , , , , , , ]
[ , , , , , , , ]
[ , , , , , , , ]
[ , , , , , , , ]

The minimum number of moves to reach each square on the board from each of these 10 types of squares are shown below. The starting square is indicated by 0.

[0,3,2,3,2,3,4,5]
[3,4,1,2,3,4,3,4]
[2,1,4,3,2,3,4,5]
[3,2,3,2,3,4,3,4]
[2,3,2,3,4,3,4,5]
[3,4,3,4,3,4,5,4]
[4,3,4,3,4,5,4,5]
[5,4,5,4,5,4,5,6], max = 6

[3,2,1,2,3,4,3,4]
[0,3,2,3,2,3,4,5]
[3,2,1,2,3,4,3,4]
[2,1,4,3,2,3,4,5]
[3,2,3,2,3,4,3,4]
[2,3,2,3,4,3,4,5]
[3,4,3,4,3,4,5,4]
[4,3,4,3,4,5,4,5], max = 5

[2,1,4,3,2,3,4,5]
[3,2,1,2,3,4,3,4]
[0,3,2,3,2,3,4,5]
[3,2,1,2,3,4,3,4]
[2,1,4,3,2,3,4,5]
[3,2,3,2,3,4,3,4]
[2,3,2,3,4,3,4,5]
[3,4,3,4,3,4,5,4], max = 5

[3,2,3,2,3,4,3,4]
[2,1,4,3,2,3,4,5]
[3,2,1,2,3,4,3,4]
[0,3,2,3,2,3,4,5]
[3,2,1,2,3,4,3,4]
[2,1,4,3,2,3,4,5]
[3,2,3,2,3,4,3,4]
[2,3,2,3,4,3,4,5], max = 5

[4,3,2,1,2,3,4,3]
[3,0,3,2,3,2,3,4]
[2,3,2,1,2,3,4,3]
[1,2,1,4,3,2,3,4]
[2,3,2,3,2,3,4,3]
[3,2,3,2,3,4,3,4]
[4,3,4,3,4,3,4,5]
[3,4,3,4,3,4,5,4], max = 5

[1,2,1,4,3,2,3,4]
[2,3,2,1,2,3,4,3]
[3,0,3,2,3,2,3,4]
[2,3,2,1,2,3,4,3]
[1,2,1,4,3,2,3,4]
[2,3,2,3,2,3,4,3]
[3,2,3,2,3,4,3,4]
[4,3,4,3,4,3,4,5], max = 5

[2,3,2,3,2,3,4,3]
[1,2,1,4,3,2,3,4]
[2,3,2,1,2,3,4,3]
[3,0,3,2,3,2,3,4]
[2,3,2,1,2,3,4,3]
[1,2,1,4,3,2,3,4]
[2,3,2,3,2,3,4,3]
[3,2,3,2,3,4,3,4], max = 4

[4,1,2,1,4,3,2,3]
[1,2,3,2,1,2,3,4]
[2,3,0,3,2,3,2,3]
[1,2,3,2,1,2,3,4]
[4,1,2,1,4,3,2,3]
[3,2,3,2,3,2,3,4]
[2,3,2,3,2,3,4,3]
[3,4,3,4,3,4,3,4], max = 4

[3,2,3,2,3,2,3,4]
[4,1,2,1,4,3,2,3]
[1,2,3,2,1,2,3,4]
[2,3,0,3,2,3,2,3]
[1,2,3,2,1,2,3,4]
[4,1,2,1,4,3,2,3]
[3,2,3,2,3,2,3,4]
[2,3,2,3,2,3,4,3], max = 4

[2,3,2,3,2,3,2,3]
[3,4,1,2,1,4,3,2]
[2,1,2,3,2,1,2,3]
[3,2,3,0,3,2,3,2]
[2,1,2,3,2,1,2,3]
[3,4,1,2,1,4,3,2]
[2,3,2,3,2,3,2,3]
[3,2,3,2,3,2,3,4], max = 4

This can be easily programmed using e.g. Dijkstra's Algorithm, and is a typical programming exercise when learning about pathfinding algorithms.