Chess Knight Minimo si sposta a destinazione su una tavola infinita

Question

Ci sono toni di soluzioni per Knights Tour o percorso più breve per i cavalieri dal movimento della cellula di origine a cella di destinazione. La maggior parte delle soluzioni utilizza BFS che sembra il miglior algoritmo.

Ecco la mia implementazione usando Hashmap:

    public class Knight_HashMap {

    static HashMap<String, Position> chessboard = new HashMap<String, Position>();
    static Queue<Position> q = new LinkedList<Position>();
    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 <= 2; i++) {
            for (int j = -2; j <= 2; j++) {

                Position next = new Position(current.x + i, current.y + j, depth);

                if (isValid(current, next)) {
                    if (inRange(next.x, next.y)) {
                        // chessboard.put(Arrays.toString(new int[] { next.x, next.y }), next);
                        // Skip if next location is same as the location you came from in previous run
                        if (current.equals(next))
                            continue;

                        Position position = chessboard.get(Arrays.toString(new int[] { next.x, next.y }));
                        if (position == null) {
                            position = new Position(Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE);
                        }
                        /*
                         * Get the current position object at this location on chessboard. If this
                         * location was reachable with a costlier depth, this iteration has given a
                         * shorter way to reach
                         */
                        if (position.depth > depth) {

                            chessboard.put(Arrays.toString(new int[] { current.x + i, current.y + j }),
                                    new Position(current.x, current.y, depth));
                            // chessboard.get(current.x + i).set(current.y + j, new Position(current.x,
                            // current.y, depth));
                            q.add(next);
                        }
                    }
                }

            }

        }

    }

    private static boolean isValid(Position current, Position next) {
        // Use Pythagoras theorem to ensure that a move makes a right-angled triangle
        // with sides of 1 and 2. 1-squared + 2-squared is 5.
        int deltaR = next.x - current.x;
        int deltaC = next.y - current.y;
        return 5 == deltaR * deltaR + deltaC * deltaC;
    }

    private static boolean inRange(int x, int y) {
        return 0 <= x && x < Nx && 0 <= y && y < Ny;
    }

}

class Position {

    public int x;
    public int y;
    public int depth;

    Position(int x, int y, int depth) {
        this.x = x;
        this.y = y;
        this.depth = depth;
    }

    public boolean equals(Position that) {
        return this.x == that.x && this.y == that.y;
    }

    public String toString() {
        return "(" + this.x + " " + this.y + " " + this.depth + ")";
    }
}

Funziona bene con una piccola dimensione ma con 10^9 x 10^9 I faccia outOfMemory eccezione. Ho anche provato con Java 2D Array, ArrayList, HashMap insieme a una lista Linked come coda. Ma per quella dimensione 10^9 x 10^9 con qualsiasi struttura di dati, ho affrontato outOfMemory eccezione.

C'è possibilità di ottimizzazione da evitare outOfMemory O qualche altro modo/struttura dati per gestire una dimensione così enorme?

Nota: Dovrei menzionare che questa domanda proviene da Contest BAPC17 di nome Knight's Marathon