My implementation of (open) Knight's Tour

Question

This is my implementation of the (open) Knight's Tour on a 5v5 board. My original assignment for CS was to solve the Knight's Tour from any startings position (0,0 -> 4,4). The goal for myself was to make this class as clean as it could be. I would like some feedback (and constructive criticism!) on the code and its performance.

I have used the StdDraw class from Princeton to display the 5v5 board with graphics.

private final int N;
private final int startX;
private final int startY;
private boolean[][] visited;
private boolean done;
private final int[][] moves = {{1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2},
        {-2, 1}, {-2, -1}, {-1, -2}}; //x, y.
private int[][] board;
private int total;    

public Board(final int N, final int startX, final int startY) {
    this.N = N;
    this.startX = startX;
    this.startY = startY;
    visited = new boolean[N][N];
    board = new int[N][N];
    init();
}

private void init() {
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++) {
            visited[x][y] = false;
            board[x][y] = -1;
        }
    }
    done = false;
    total = N * N;
}

public boolean solve() {
    board[startX][startY] = 0;
    return solve(startX, startY, 0);
}

private boolean solve(int x, int y, int currentMove) {
    if ((x < 0) || (x >= N) || (y < 0) || (y >= N)) return false;
    if (done || visited[x][y]) return false;

    visited[x][y] = true;
    board[x][y] = currentMove;

    final List<int[]> moves = movesList(x, y);

    if (moves.isEmpty())
        return false;

    if (hasVisitedAll()) {
        done = true;
    }

    StdDraw.setPenColor(Color.BLUE);

    if (x == startX && y == startY)
        StdDraw.setPenColor(StdDraw.RED);

    StdDraw.filledCircle(x + 0.5, y + 0.5, 0.25);
    StdDraw.show(1_000); //1sec per next move

    for (final int[] m : moves) {
        int x2 = m[0];
        int y2 = m[1];

        if (solve(x2, y2, currentMove + 1)) {
            board[x2][y2] = currentMove + 1;
            return true;
        } else if (isLegitMove(x2, y2)) {
            visited[x2][y2] = false;
        }
    }
    return done;
}

private boolean hasVisitedAll() {
    int count = 0;
    for (final int[] v : board) {
        for (final int v2 : v) {
            if (v2 >= 0) count++;
        }
    }
    return (count == total);
}

private List<int[]> movesList(final int x, final int y) {
    final List<int[]> move = new ArrayList<>();
    for (int[] m : moves) {
        int x2 = m[0];
        int y2 = m[1];
        move.add(new int[]{x + x2, y + y2});
    }
    return move;
}

private boolean isLegitMove(final int x, final int y) {
    return ((x > 0 && x < N)) && ((y > 0 && y < N));
}

Answer 1

• final List<int[]> moves local to solve shadows private final int[][] moves member. While it may not affect the functionality, it surely makes code harder to understand.

• I don't see how moves.isEmpty() could ever be satisfied.

• Dealing with visited squares looks suspiciously redundant:

  • The all squares visited condition is directly derived from currentMove value: currentMove == total, so there is no need to scan the entire visited array.

  • Similarly, a square visited condition could be implicitly derived from the corresponding board[][] value. Initially, it is -1 for unvisited squares - and you may maintain this invariant by resetting the board[][] to -1 instead of setting visited[][] to false.

  This means that you may eliminate visited[][] array.

• An x > 0 condition in isLegitMove looks strange, as if the indexing starts with 1 (according to the rest of the program logics it starts with 0). I am not sure I understand why x == 0 makes the move illegitimate. Looks like a potential bug.