1
$\begingroup$

I was thinking about how to write a computer program to find the path with minimal number of moves that takes a knight from one square $(x_1,y_1)$ to another square $(x_2,y_2)$ on an unbounded chess board. It occurred to me this might not be as computationally challenging as it seems. If both $|x_1 - x_2|$ and $|y_1 - y_2|$ are large, then it seems like then any optimal solution will be primarily the two moves that move 2 squares toward $x_2$ and 1 square toward $y_2$, or move 2 squares toward $y_2$ and 1 square toward $x_2$. (And e.g. if we reach $(x,y)$ where $|x - x_2|$ is large but $|y - y_2|$ isn't, then we alternate between the two moves that move two squares toward $x_2$. Then as soon as we reach a square $(x,y)$ where $|x - x_1|$ and $|y - y_1|$ are both less than some small-ish value (maybe like 10), then we need a computer to find the optimal solution, and this should give the global optimal solution if my hunch is correct. But I don't know how to prove it. Can someone come up with a proof, and hopefully minimize the threshold on $|x - x_1|$ and $|y - y_1|$ where direct computation is needed to finish finding the optimal path?

$\endgroup$
  • $\begingroup$ If it's a greedy algorithm, you are looking for the "best" choice at each step. This should be the move that minimizes the distance between the point you are on and the point you want to get to with distance being sqrt($(x_1 - x_2)^2 + (y_1 - y_2)^2$). A greedy algorithm does not always give you a global optimum or even a local optimum and it doesn't have to. $\endgroup$ – user137481 Aug 12 '14 at 16:47
0
$\begingroup$

You really do not want to arrive at $(x_2\pm2,y_2\pm2)$ as those require $4$ moves to finish and the previous positions only required $3$, so it is best to be careful once both gaps are $4$ or less.

But further away than that, the rings of optimal positions around the finish are essentially octagonal, so a sensible simple approach will work.

It might be best to describe this sensible simple approach as narrowing the larger gap by $2$ and the smaller one by $1$ (choosing either sensible possibility when the two gaps have the same magnitude, and either sensible possibility when a gap is $0$).

This is table of positions which require $4$ moves or fewer to finish

.   .   .   .   4   .   4   .   4   .   4   .   4   .   .   .   .
.   .   .   4   .   4   .   4   .   4   .   4   .   4   .   .   .
.   .   4   .   4   3   4   3   4   3   4   3   4   .   4   .   .
.   4   .   4   3   4   3   4   3   4   3   4   3   4   .   4   .
4   .   4   3   4   3   2   3   2   3   2   3   4   3   4   .   4
.   4   3   4   3   2   3   2   3   2   3   2   3   4   3   4   .
4   .   4   3   2   3   4   1   2   1   4   3   2   3   4   .   4
.   4   3   4   3   2   1   2   3   2   1   2   3   4   3   4   .
4   .   4   3   2   3   2   3   0   3   2   3   2   3   4   .   4
.   4   3   4   3   2   1   2   3   2   1   2   3   4   3   4   .
4   .   4   3   2   3   4   1   2   1   4   3   2   3   4   .   4
.   4   3   4   3   2   3   2   3   2   3   2   3   4   3   4   .
4   .   4   3   4   3   2   3   2   3   2   3   4   3   4   .   4
.   4   .   4   3   4   3   4   3   4   3   4   3   4   .   4   .
.   .   4   .   4   3   4   3   4   3   4   3   4   .   4   .   .
.   .   .   4   .   4   .   4   .   4   .   4   .   4   .   .   .
.   .   .   .   4   .   4   .   4   .   4   .   4   .   .   .   .
$\endgroup$

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.