Trapped Knight Problem

SquareSpiral.java

import java.util.*;

public class SquareSpiral {
    // Starting point of the spiral
    private final int startX;
    private final int startY;

    private SquareSpiral(int startX, int startY) {
        this.startX = startX;
        this.startY = startY;
    }

    public static void main(String[] args) {
        SquareSpiral spiral = new SquareSpiral(0, 0);

        // Legal movements of a knight
        Point[] movements = new Point[] {
                new Point(-1, -2), new Point(1, -2),
                new Point( -2, -1), new Point(2, -1),
                new Point( -2, 1), new Point(2, 1),
                new Point(-1, 2), new Point(1, 2)
        };

        int x = 0;
        int y = 0;

        List<Point> path = new ArrayList<>();
        Set<Point> visited = new HashSet<>();

        Point startPoint = new Point(0, 0);
        path.add(startPoint);
        visited.add(startPoint);

        for (int i = 1; i < 50000; i++) {
            //System.out.println("Step " + i + ", x: " + x+ ", y: " + y + " = " + spiral.getCellIndex(x, y));

            // Now find the smallest next value
            int bestScore = Integer.MAX_VALUE;
            int bestIndex = -1;

            for (int j = 0; j < movements.length; j++) {
                Point movement = movements[j];
                int x1 = movement.getX() + x;
                int y1 = movement.getY() + y;

                // Skip previously visited cells
                if (visited.contains(new Point(x1, y1))) {
                    continue;
                }
                int currentScore = spiral.getCellIndex(x1, y1);

                if (currentScore < bestScore) {
                    bestScore = currentScore;
                    bestIndex = j;
                }
            }
            if (bestIndex < 0) {
                System.out.println("Trapped in step " + i + ", x: " + x+ ", y: " + y + " = " + spiral.getCellIndex(x, y));

                // Remove current point
                path.remove(path.size() - 1);

                // Go to previous point
                Point prev = path.get(path.size() - 1);
                x = prev.getX();
                y = prev.getY();
                i--;
            } else {
                x += movements[bestIndex].getX();
                y += movements[bestIndex].getY();

                Point nextPoint = new Point(x, y);
                visited.add(nextPoint);
                path.add(nextPoint);
            }
        }
    }

    private int getCellIndex(int x, int y) {
         /*
            Consider the following square spiral:
               x   -2 -1  0  1  2
              y  ------------------
             -2  | 17 16 15 14 13
             -1  | 18 05 04 03 12
              0  | 19 06 01 02 11
              1  | 20 07 08 09 10
              2  | 21 22 23 24 25   ...

             The spiral starts at point (0, 0), marked as 01. It then moves in a square around 01, starting at
             02 and ending at 09. Let this be square index 1. Next, the spiral moves in another square,
             starting from 10 and ending at 25. Let this be square index 2, and so on.

             It is this square index we compute next:
         */
        int squareIndex = Math.max(Math.abs(x - startX), Math.abs(y - startY));

        // Compute the number of the cell at the top-left corner of the square. In square 1, this would be 05,
        // and in square 2, this is 17, and so on.
        int squareMiddleNumber = 4 * squareIndex * squareIndex + 1;

        // The coordinates of the top-left corner in the square
        int squareMiddleX = startX - squareIndex;
        int squareMiddleY = startY - squareIndex;

        // Do point (x, y) come before or after the top-left corner in the sequence
        if (y >= x) {
            // Point comes after in the sequence - add the value of the top-left corner to the manhattan distance
            // of our current point
            return squareMiddleNumber + Math.abs(squareMiddleX - x) + Math.abs(squareMiddleY - y);
        } else {
            // As above, only we subtract the manhattan distance
            return squareMiddleNumber - Math.abs(squareMiddleX - x) - Math.abs(squareMiddleY - y);
        }
    }

    /**
     * An integer point in 2D space.
     */
    public static class Point {
        private final int x;
        private final int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x &&
                    y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }
}