Chess Knight minimum moves to destination on an infinite board

There are tones of solutions for Knights tour or shortest path for Knights movement from source cell to destination cell. most of the solutions are using BFS which seems the best algorithm.

Here is my implementation using HashMap:

```
public class Knight_HashMap {

static HashMap chessboard = new HashMap();
static Queue q = new LinkedList();
static int Nx, Ny, Kx, Ky, Cx, Cy;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("insert Board dimentions: Nx, Ny");
Nx = sc.nextInt();
Ny = sc.nextInt();
System.out.println("inset Knight's location: Kx, Ky");
Kx = sc.nextInt();
Ky = sc.nextInt();
System.out.println("insert destination location: Cx, Cy");
Cx = sc.nextInt();
Cy = sc.nextInt();
sc.close();

// Assume the position for simplicity. In real world, accept the values using
// Scanner.
Position start = new Position(Kx, Ky, 0); // Positionition 0, 1 on the chessboard
Position end = new Position(Cx, Cy, Integer.MAX_VALUE);

chessboard.put(Arrays.toString(new int[] { Kx, Ky }), new Position(Kx, Ky, 0));

q.add(start);

while (q.size() != 0) // While queue is not empty
{
Position pos = q.poll();
if (end.equals(pos)) {
System.out.println("Minimum jumps required: " + pos.depth);
return;
} else {
// perform BFS on this Position if it is not already visited
bfs(pos, ++pos.depth);
}
}

}

private static void bfs(Position current, int depth) {

// Start from -2 to +2 range and start marking each location on the board
for (int i = -2; i depth) {

chessboard.put(Arrays.toString(new int[] { current.x + i, current.y + j }),
new Position(current.x, current.y, de

The easiest way to solve this problem is to greedily move in the best direction until you get within 100 squares or so, and then A* from there.

Figuring out exactly how close you can get before you have to switch to A is an interesting problem, but 100 squares away will surely be fine, and A from there fits into a reasonable amount of memory.

Also note that the greedy portion will only involve 1 or 2 types of moves, and it's not hard to figure out how many of each type you will do without making an individual decision for each one.

EDIT: Since this is the CS stack I guess I should prove that it works. OK:

By symmetry I only need to consider two cases:

Case 1 -- 2 >= dx/dy >= 1/2

In this case, the greedy portion will choose between move near the diagonal. Each move reduces the manhattan distance to target by 3, and all other moves will decrease the manhattan distance by at best 1.

Lets say the length of the longest path of greedy moves is N. That path will get to a position at most 3 moves away from the target, so the best path length is at most N+3.

Now, if I use only N-m moves from the greedy path, then I will be left at a position at manhattan distance at least 3m, and it will take at least 3m moves to correct that, so the best achievable path length would be N-m+3m. If that is gonna be = dx/dy >= -1/2:

In this case, the greedy portion will consist of moves near the horizontal. Each greedy move will reduce the x distance by 2, and all other moves will reduce it by at most 1.

Again the longest greedy path (length N) will get within 3 moves. If we make N-m greedy moves, we are left at x distance at least 2m, and require 2m moves to fix it. If the best path consists of only N-m greedy moves, we need N+m < N+3, so the bast path can have at least N-2 elements from the longest greedy path.

Conclusion:

We can do much better than getting within 100 squares. Calculate the moves in the longest greedy path, and remove 2 moves of each type (up to the total number of moves of that type, if it contains less), and we will be left with only moves that can be part of a shortest path.

That will get us within 8 squares, and A* from there will not be expensive.

StackExchange Computer Science Q#97903, answer score: 5