Knight's tour / recursion

Question

I'm trying to learn a little bit more about recursion but somehow I can't solve the knight's tour and I'm hoping someone can point out my logic error.

class main {

    static int fsize = 5; // board size (5*5)
    static int board[][] = new int[fsize][fsize];
    static int[] move_x = {1, 2, 2, 1, -1, -2, -2, -1}; // possible moves (x-axis)
    static int[] move_y = {-2, -1, 1, 2, 2, 1, -1, -2}; // possible moves (y-axis)

    // x = current x coordinate
    // y = current y coordinate
    static void Solve(int move_number, int x, int y) {
        board[x][y] = move_number;

        // check whether the knight has been on all filds or not
        if (move_number == ((fsize * fsize) - 1)) {
            for (int i = 0; i < fsize; i++) {
                for (int c = 0; c < fsize; c++) {
                    System.out.printf("%3d", board[i][c]);
                }
                System.out.println("\n");
            }
        } 
        else {
            // calculate new board coordinates
            for (int i = 0; i < 8; i++) {
                for (int c = 0; c < 8; c++) {
                    // Check whether the new coordinates are valid or not
                    if ((x + move_x[i]) >= 0 && (x + move_x[i]) < fsize && (y + move_y[c]) >= 0 && (y + move_y[c]) < fsize) {
                        // check whether the knight has been on this field or not (-1 = hasn't been here)
                        if (board[x + move_x[i]][y + move_y[c]] == -1) {
                            System.out.println("Move: " + move_number + "\n");
                            // Find next field
                            Solve(move_number + 1, (x + move_x[i]), (y + move_y[c]));
                        }
                    }
                }
            }
            // couldn't find a valid move
            board[x][y] = -1;
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < fsize; i++) {
            for (int c = 0; c < fsize; c++) {
                board[i][c] = -1;
            }
        }

        Solve(0, 0, 0);
    }
}

Edit: hope this is ok. I tried to run this program but couldn't get more than 22 valid moves.

Answer 1

I was able to fix your code by doing two things:

• Only use for (int i = 0; i < 8; i++) single-level loop to check for the next 8 possibilities
  • Why do you have two nested loops here? You just want to check those 8 possibilities, that's it.
  • There are only 8 moves at each level, not 64
• Make board[x][y] = -1; the last statement in Solve
  • You want this executed regardless of the if conditions
  • You HAVE to undo board[x][y] = move_number; before you exit from this level

After fixing those, your homework is done, correct, finished. Congratulations!

---

In pseudocode

Right now, this is what you have:

static void Solve(int move_number, int x, int y) {
    board[x][y] = move_number;

    if (DONE) {
       PRINT;
    } else {
        for (int i = 0; i < 8; i++) {
            for (int c = 0; c < 8; c++) {
                ATTEMPT_MOVE(i, c); // doesn't make sense!!!
            }
        }
        board[x][y] = -1; // this doesn't belong here!!!
    }
}

To fix this code, you just have to do this:

static void Solve(int move_number, int x, int y) {
    board[x][y] = move_number;

    if (DONE) {
       PRINT;
    } else {
        for (int i = 0; i < 8; i++) {
           ATTEMPT_MOVE(i); // now makes more sense!
        }
    }

    board[x][y] = -1; // must undo assignment in first line!
}

---

Extra suggestions

• Break down logic into helper methods, i.e. board printing, and checking for valid coordinates