9
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Ari Feb 5 '15 at 23:50
  • 1
    $\begingroup$ 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?. $\endgroup$ – AlexR Feb 5 '15 at 23:52
  • $\begingroup$ 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? $\endgroup$ – HammyTheGreek Feb 6 '15 at 0:26
  • $\begingroup$ No...a mathematical problem $\endgroup$ – user157835 Feb 6 '15 at 8:00
12
$\begingroup$

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:

corner-knight moves

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:

midboard-knight moves

diagonally-adjacent squares are reached more quickly.


Additional thought:

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}$$

$\endgroup$
  • $\begingroup$ What is delta x and delta y here and ...how you get this results ..means specific formula $\endgroup$ – user157835 Feb 13 '15 at 18:57
  • $\begingroup$ $\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). $\endgroup$ – Joffan Feb 13 '15 at 18:58
  • $\begingroup$ 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. $\endgroup$ – Joffan Feb 13 '15 at 19:16

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.