# minimum number of steps for knight in chess

Given two squares on an 8×8 chess board, how can we determine the minimum number of moves required by a knight to reach one square starting from the other?

• The absolute minimum would be one (disallowing choosing the same point twice). Do you mean the min-max, i.e. best solution to the worst case scenario? In other words: What is the maximum number of moves required to move a Knight between two squares on a chessboard? – Ari Feb 5 '15 at 23:50
• I suppose you mean something different from what you actually asked. If you need help formulating and I'm right, try this: Given two squares on an $8\times 8$ chess board, how can we determine the minimum number of moves required by a knight to reach one square starting from the other?. – AlexR Feb 5 '15 at 23:52
• Formulate the possible moves as a graph, with all valid moves from one square to another as edges between vertices. Do a DFS from start to finish positions... There's also a direct formula for this so it's $O(1)$. Is this a programming contest question? – HammyTheGreek Feb 6 '15 at 0:26
• No...a mathematical problem – user157835 Feb 6 '15 at 8:00

If you were considering an infinite chess board, you might get a solution as a (slightly complicated) formula, but on a finite board the restriction of edges (and especially corners) does affect things. Obviously you can draw maps: And there you can see that the corner position of the knight means that it is quite slow to reach its diagonally neighbouring square, whereas with an open-board knight: diagonally-adjacent squares are reached more quickly.

Outside the $5\times 5$ square centred on the knight, the move-distance pattern becomes simpler. Then if you find $\Delta x, \Delta y$ (unsigned), compute the maximum of $\left ( \frac{\Delta x}{2},\frac{\Delta y}{2},\frac{\Delta x+\Delta y}{3} \right )$ and round up to the nearest integer. Call this $m'$. Now calculate the move count $m$ as follows: $$m=m'+((m'+\Delta x+\Delta y) \bmod 2)$$ To handle close-in squares (on a board of at least $5\times 5$) we can list the exceptions: \begin{align} \Delta x =\Delta y =2 &\implies m=4 \\ \Delta x+\Delta y =1 &\implies m=3 \\ \text{For a knight in a corner only, }\Delta x=\Delta y =1 &\implies m=4 \hspace{3in} \end{align}
• $\Delta x$ and $\Delta y$ are the difference in square position in $x$ and $y$ directions (it doesn't matter which direction is which). A normal knight move has $\Delta x=1$ and $\Delta y=2$ (or the other way around). – Joffan Feb 13 '15 at 18:58
• Basically there is a "distance" away from the the knight which is important - that get us to $m'$ - and there is a square color adjustment, which takes us to $m$. Then as you see there are special cases for short distances. – Joffan Feb 13 '15 at 19:16