5

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.

6
  • 1
    The question title implies you want to visit all of the squares on the board? Which would be a en.wikipedia.org/wiki/Knight%27s_tour . However judging by the text your question would be more along the lines of which two squares are "furthest apart" for a knights? Some clarification would be good. – koedem Mar 25 at 4:02
  • Thank's for pointing out the resource. I've edited my question @koedem – eguneys Mar 25 at 4:27
  • 1
    I am still confused as to what is sought – Laska Mar 25 at 5:52
  • which two squares takes a knight to travel the maximum number of moves, and what is that number. – eguneys Mar 25 at 6:07
  • Is your "minimum number of iterations needed for looking at piece moves" the same as "minimum moves to get from one place to any other" or not? – Robbie Goodwin Mar 25 at 22:00
13

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

5
  • 6
    Good stuff. 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 Mar 25 at 9:51
  • 1
    @Laska Nice! I guess you don't want to post your own answer, since you already did and deleted it. So I took the liberty of quoting your improvement in my answer. Feel free to roll back my last edit if you object to being quoted. – bof Mar 25 at 10:12
  • You're fine bof: you'd done 90% of it :D Thanks for the quote :) – Laska Mar 25 at 11:39
  • 1
    It's long enough that moving the knight requires a careful plan, and long enough that a knight one square out of position has virtually no hope of engaging before the dust settles. – J... Mar 25 at 15:04
  • 1
    That at least 6 moves are necessary is perhaps easier to see in the taxicab metric; the distance between the two corner squares is 14, and the distance traveled in each move is 3, so you need at least 5 moves. – user27149 Mar 25 at 20:22
3

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.

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.