3
\$\begingroup\$

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));
}
\$\endgroup\$
1
\$\begingroup\$
  • 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.

\$\endgroup\$

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.