# minimum moves for Knight on a infinite chessboard [duplicate]

You are given an infinite chessboard, a knight, a source and a destination.(Normal chess rules apply) we are required to get move knight from source to destination in minimum moves possible.

I can only think of a bfs solution. Is there a better solution possible?

The question is further extended by adding obstacles to the board. How to solve this question what will be the complexity.(I basically need a answer for this.)

Thank you.

## 2 Answers

With obstacles, you can use an algorithm as it is used for routing the shortest car distance. The idea is that you perform a search not breadth first, but with moves first that get you closer to the target. And you start from both ends and meet in the middle.

Define the "optimal distance" between points as the distance given by the algorithm for lowest number of moves without obstacles. At the starting point, find all neighbouring points, and for each calculate a lower bound for the number of moves to the target: One initial move, and the moves for the closest distance to the target. Then the same from the other end. Next you examine those points with the lowest lower bound. All moves are eventually evaluated, bot you tend to check those first that get you closer to the target.

• i am working on a problem like this currently. my approach so far was the same you described, but is still ineffective, because i do nothing with the information i get when the two clusters meet. Could you elaborate on what you mean by meeting the searches "in the middle"? it should be impossible to know if it's really the shortest path we found, when two clusters meet. But i know there is a path and i get an upper bound for the minimum path length. my best bet is to not expand those "merged" paths that are below above this bound but that is even slower, due to more data structure lookups. – Falco Winkler Aug 15 '20 at 19:27

Without obstacles you can solve this in constant time. You'll have to work the details out, but the idea is that in two moves if you want to cover distance you can move 4 steps in one direction and 0 or 2 in the either, or 3 steps in each direction. So let's say the distance is (100, 48): You do 24 double moves (4, 2) plus 1 double move (4, 0). Let's say the distance is (100, 60): You move diagonally until one distance is half the other, say 8 double moves (3, 3) leaving a distance of (76, 36) which can be covered in 19 double moves.

You make a small table of how to best cover small distances: (0, 0) takes 0 moves, (1, 0) takes three moves, (1, 1) takes two moves, (2, 0) takes two moves, (2, 1) takes 1 move, (2, 2) takes 4 moves, etc. And you are left with a small number of possibilities how to go a large distance in the fastest way, followed by a small distance.