1
$\begingroup$

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<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 + ")";
    }
}

This works well with small dimension but with 10^9 x 10^9 I face outOfMemory exception. I also tried with java 2d array, ArrayList, HashMap alongside with a LinkedList as Queue. but for that dimension 10^9 x 10^9 with any data structure, I face outOfMemory exception.

Is there possibility of optimization to avoid outOfMemory or anyother way/data structure to handle such huge dimension?

Note: I should mention this question is from BAPC17 contest named Knight's Marathon

$\endgroup$

migrated from stackoverflow.com Sep 29 '18 at 7:56

This question came from our site for professional and enthusiast programmers.

  • 5
    $\begingroup$ 10^9 x 10^9 bytes == 10^18 bytes == 1 exabyte == 1,000 petabytes == 1,000,000 terabytes == 1,000,000,000 gigabytes. How big is your machine? $\endgroup$ – Stephen C Sep 29 '18 at 7:23
  • $\begingroup$ @StephenC Yes I know and this is why I am asking this question here. for sure the solution is not famous 2d array with BFS $\endgroup$ – Amir-Mousavi Sep 29 '18 at 7:25
  • 1
    $\begingroup$ Start here: sciencedirect.com/science/article/pii/S0166218X05000880 $\endgroup$ – Stephen C Sep 29 '18 at 7:37
  • 1
    $\begingroup$ If you're looking for shortest paths, what's the hash map for? $\endgroup$ – Raphael Sep 29 '18 at 10:54
  • 1
    $\begingroup$ @huseyintugrulbuyukisik This is a straightforward combinatorial serach problem. There's no reason whatsoever to use randomized, unpredictable techniques such as genetic algorithms. $\endgroup$ – David Richerby Oct 1 '18 at 13:08
5
$\begingroup$

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 < N+3, then m < 2, so the shortest path includes at least N-1 moves from a longest greedy path.

Case 2 -- 1/2 >= 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.

$\endgroup$
  • $\begingroup$ Thanks, it now makes more sense. can you also explain a bit more about Greedily Move? limit moves to (+2,+1) and (+1,+2) but how check if we are in the correct direction? $\endgroup$ – Amir-Mousavi Sep 30 '18 at 19:20
  • $\begingroup$ Say you have to go distance dx in x and dy in y. If you go do N (2,1) moves and M (1,2) moves, then you will go (2N+M, 2M+N) in total. Solve (2N+M)/(2M+N) = dx/dy to get the ratio of the different move types. $\endgroup$ – Matt Timmermans Sep 30 '18 at 21:35
  • $\begingroup$ Thanks, that was a good hint and changed my search direction and found the solution. posted here as Answer $\endgroup$ – Amir-Mousavi Oct 1 '18 at 4:48
  • $\begingroup$ Honestly, this is probably over-complicating things. Just using A* with an appropriate metric should just run towards the goal and then make adjustments at the end. $\endgroup$ – David Richerby Oct 1 '18 at 13:03
  • $\begingroup$ @DavidRicherby that's true, but with board size 10^9 even that initial run is a lot of work. $\endgroup$ – Matt Timmermans Oct 1 '18 at 15:05
4
$\begingroup$

There is a closed form solution for finding the minimum number of moves the chess knight needs to move a specified displacement on the infinite chess board. Let $g$ be the requisite displacement expressed as a Gaussian integer; the real part of $g$ will be the horizontal displacement, and the imaginary part of $g$ will be the vertical displacement. Then we may write

$$g = ((1-i)g+(2-i)d)(2+i) - (g+(2+i)d)(2-i). $$

Here, $d$ can be any Gaussian integer; the value of $d$ which minimizes the number of knight moves is $d=Cint((2i-5)g/10)$, where $Cint$ is the closest Gaussian integer of the argument. The first term yields the requisite counterclockwise moves, and the second term yields the requisite clockwise moves. The real and imaginary parts of the counterclockwise and clockwise coefficients together yield the total minimum requisite moves of the chess knight, while simultaneously specifying all minimal paths.

N.B. Reply to amass.jack

I am an originator of this formula. I do not yet know of any prior publication. However, I have generated lecture notes for my talk at Acacia Creek to be given on the third Wednesday in February, as well as additional notes with numerous worked examples. These notes set forth the fundamental theory providing a foundation for the formula. Robert Word, Ph.D.

I have encountered difficulties in activating the present interface to post a reply to you, for unclear reasons. Hence, I copied the same reply into a number of related Facebook groups dealing with Mathematics, in case you might happen across them.

$\endgroup$
  • 1
    $\begingroup$ For those who might not be familiar with the term, a Gaussian integer is a complex number whose real and imaginary parts are integers. $\endgroup$ – David Richerby Jan 26 at 21:56
  • 1
    $\begingroup$ Can you add a reference to where the formula is obtained? It might be even better if you can prove it in the answer. $\endgroup$ – Apass.Jack Jan 27 at 3:47
  • $\begingroup$ Hi, Robert. It looks like you've created two accounts. You can merge them by following these instructions. Then you'll be able to comment on your own posts, and also edit them without needing our approval. $\endgroup$ – David Richerby Jan 27 at 10:41
  • $\begingroup$ Greetings! It would be useful to consult with the paper by P.P Das and B.N. Chaterjee, “Knight’s distance in digital geometry”, published in Pattern Recognition Letters, 7 (1988) 215-226. The second page of their paper sets forth the requisite closed form expression for the Knight’s distance. $\endgroup$ – Robert Wordar Feb 18 at 2:12
  • $\begingroup$ The second caveat is that the value of d minimizing the knight’s distance in the closed form expression that I have given is approximate rather than exact. It is necessary to search around this value to locate all values which minimize the knight’s distance. This project is facilitated by using the closed form expression of Das and Chatterji. In this way, it is possible to find all possible minimal paths of the chess knight. $\endgroup$ – Robert Wordar Feb 18 at 2:17
0
$\begingroup$

How far does it scale currently? If you get close, some tweaks may help. If you approach doesn't scale at all (which I suspect), you'll need to reconsider the approach in general.

Some ideas:

  1. BFS uses more memory than DFS (e.g. A*), as you need to keep more data in memory. For this problem, you could prioritize moves that go into the general direction.

  2. String keys seem to be quite wasteful. Consider using a specialized data structure for sparse 2d arrays (I have implemented one here, you'll probably find more / better ones on the net). Or use a Position2D hash key.

  3. Do you need all this data in Position?

  4. Can you exploit the structure of the moves in some way? Are there some constraints that you can exploit? Do you need the full grid?

$\endgroup$
0
$\begingroup$

thanks to matt timmermans by his hint I realized for infinite chess boards no search algorithm BFS, DFS, A*, Dijkstra should be used. just calculate diagonal symmetry and imagine that start point as (0,0). just 2 corners should be hardcoded. adopted from here

System.out.println((int) distance(ENDx - STARTx, ENDy - STARTy));    
public static double distance(int x, int y) {
        // axes symmetry
        x = Math.abs(x);
        y = Math.abs(y);
        // diagonal symmetry
        if (x < y) {
            int t = x;
            x = y;
            y = t;
        }
        // 2 corner cases
        if (x == 1 && y == 0) {
            return 3;
        }
        if (x == 2 && y == 2) {
            return 4;
        }

        // main formula
        int delta = x - y;
        if (y > delta) {
            return (delta - 2 * Math.floor((float) (delta - y) / 3));
        } else {
            return (delta - 2 * Math.floor((delta - y) / 4));
        }
    }
$\endgroup$
  • $\begingroup$ Please, this isn't a coding site. You were asked to remove the huge code dump from your question because it's not appropriate here. It's also not appropriate for an answer. $\endgroup$ – David Richerby Oct 1 '18 at 13:04
  • 1
    $\begingroup$ @David Richerby please Tell this to the moderator who shifted my question from stackoverflow to here. $\endgroup$ – Amir-Mousavi Oct 1 '18 at 13:07

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.