Answers.Body: <p>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:</p>
  <pre>
  [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]
  </pre>
  <p>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:</p>
  <pre>
  [6, , , , , , , ]
  [5,5, , , , , , ]
  [5,5,4, , , , , ]
  [5,4,4,4, , , , ]
  [ , , , , , , , ]
  [ , , , , , , , ]
  [ , , , , , , , ]
  [ , , , , , , , ]
  </pre>
  <p>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.</p>
  <pre>
  [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
  </pre>
  <p>This can be easily programmed using e.g. <a href="https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" rel="noreferrer">Dijkstra's Algorithm</a>, and is a typical programming exercise when learning about <a href="https://en.wikipedia.org/wiki/Pathfinding" rel="noreferrer">pathfinding</a> algorithms.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-26T06:03:43.973Z
Answers.LastActivityDate: 2021-03-26T06:20:29.307Z
Answers.LastEditDate: 2021-03-26T06:20:29.307Z
Answers.UserDisplayName: New User
Answers.Body: <p>You are asking for the <a href="https://en.wikipedia.org/wiki/Distance_(graph_theory)" rel="noreferrer">diameter</a> of the <a href="https://en.wikipedia.org/wiki/Knight%27s_graph" rel="noreferrer">knight's graph</a>. I suppose you only want it for the ordinary 8x8 chessboard. (See <a href="http://oeis.org/A232007" rel="noreferrer">OEIS sequence A232007</a> 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 &gt; 4.)</p>
  <p>The answer is 6. It takes 6 moves to get from a corner square to the opposite corner, say from a8 to h1.</p>
  <p>There are many ways to get from a8 to h1 in 6 moves, e.g. a8-c7-e8-g7-h5-g3-h1.</p>
  <p>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) &lt; 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.</p>
  <p>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.</p>
  <p>I. Starting from e4, you can reach any square in at most 3 moves, <strong>except</strong> the squares a8, c2, c6, g2, g6.</p>
  <p>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.</p>
  <p>II. Therefore, a knight can get from any square to any other via e4 in at most 6 moves, <strong>unless</strong> at least one of the two squares is a8, c2, c6, g2, or g6.</p>
  <p>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.</p>
  <p>IV. From c2 (or g6) you can reach any square in at most 5 moves.</p>
  <p>V. From g2 you can reach any square in at most 5 moves.</p>
  <p>VI. From a8 you can reach any square in at most 6 moves.</p>
  <p>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>
  <p><strong>P.S.</strong> @Laska pointed out in <a href="https://chess.stackexchange.com/questions/34588/how-much-tempo-needed-for-a-knight-to-visit-any-two-squares/34589#comment55063_34589">a comment</a> that this argument can be simplified:</p>
  <blockquote>
  <p>I think the sufficiency argument can be simplified as the e4 statement also works for e5, d4 &amp; 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 &amp; 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</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-25T09:51:47.623Z
Answers.Text: 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.
Answers.UserDisplayName: Laska
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-25T10:12:42.053Z
Answers.Text: @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.
Answers.UserDisplayName: bof
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-25T11:39:49.630Z
Answers.Text: You're fine bof: you'd done 90% of it :D Thanks for the quote :)
Answers.UserDisplayName: Laska
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-25T15:04:12.800Z
Answers.Text: 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.
Answers.UserDisplayName: J...
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-25T07:57:16.423Z
Answers.LastActivityDate: 2021-03-25T10:13:32.100Z
Answers.LastEditDate: 2021-03-25T10:13:32.100Z
Answers.UserDisplayName: bof
Body: <p>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.</p>
  <p>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.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-25T04:02:07.443Z
Comments.Text: The question title implies you want to visit all of the squares on the board? Which would be a https://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.
Comments.UserDisplayName: koedem
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-25T04:27:26.237Z
Comments.Text: Thank's for pointing out the resource. I've edited my question @koedem
Comments.UserDisplayName: eguneys
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-25T05:52:12.453Z
Comments.Text: I am still confused as to what is sought
Comments.UserDisplayName: Laska
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-25T06:07:16.313Z
Comments.Text: which two squares takes a knight to travel the maximum number of moves, and what is that number.
Comments.UserDisplayName: eguneys
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-25T22:00:05.463Z
Comments.Text: 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?
Comments.UserDisplayName: Robbie Goodwin
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-25T22:18:06.030Z
Comments.Text: every iteration makes a knight move from one place to other so yes it's the same.
Comments.UserDisplayName: eguneys
Tags: <mathematics><tempo>
Title: How many moves needed for a knight to go from any square to any other square?
ThreadText: # How many moves needed for a knight to go from any square to any other square?
  
  (Asked by: username_0 on 2021-03-25)
  
  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.
  
  **Tags:** mathematics, tempo
  
  > **Comments:**
  > **username_1**: The question title implies you want to visit all of the squares on the board? Which would be a https://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.  
  > **username_0**: Thank's for pointing out the resource. I've edited my question @username_1  
  > **username_2**: I am still confused as to what is sought  
  > **username_0**: which two squares takes a knight to travel the maximum number of moves, and what is that number.  
  > **username_3**: 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?  
  > **username_0**: every iteration makes a knight move from one place to other so yes it's the same.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_5 on 2021-03-25. Score: 15 | Accepted answer
  
  You are asking for the [diameter](https://en.wikipedia.org/wiki/Distance_(graph_theory)) of the [knight's graph](https://en.wikipedia.org/wiki/Knight%27s_graph). I suppose you only want it for the ordinary 8x8 chessboard. (See [OEIS sequence A232007](http://oeis.org/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.** @username_2 pointed out in [a comment](https://chess.stackexchange.com/questions/34588/how-much-tempo-needed-for-a-knight-to-visit-any-two-squares/34589#comment55063_34589) 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. – username_2
  
  > **Comments:**
  > **username_2**: 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.  
  > **username_5**: @username_2 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.  
  > **username_2**: You're fine username_5: you'd done 90% of it :D Thanks for the quote :)  
  > **username_6**: 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.  
  
  ---
  
  ### Answer by username_4 on 2021-03-26. Score: 5
  
  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.
  
  
  ---
  
  