CODEWITHSUNDEEP
javarecursiongraph-algorithmbacktrackingknights-tour
Behnaz
Behnaz

Reputation: 63

Knight's tour recursion doesn't find a solution

Knight's tour was asked before, but I'm still having trouble with it. I'm trying a recursion to visit all cells of chessboard but I can't make more than 52 visits. After that it backtracks and the number of visited cells counts down. Here is my code:

public class Ch7E22_3 {
    public static int[][] chess;
    public static int[][] adjacent;

    public static void main(String[] args) {
        chess = new int[8][8];
        adjacent = new int[][] { { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 }, { 1, 2 }, { -1, 2 }, { 1, -2 },
                { -1, -2 } };
        initializeChess();
        move(1, 0, 0);
    }

    private static void move(int cnt, int row, int col) {
        chess[row][col] = cnt;
        if (cnt == (8 * 8)) {
            System.out.println("You moved around all cells: " + cnt);
        } else {
            for (int i = 0; i < 8; i++) {
                if (((row + adjacent[i][0] >= 0) && (row + adjacent[i][0]) < 8)
                        && ((col + adjacent[i][1] >= 0) && (col + adjacent[i][1] < 8))) {
                    if (chess[row + adjacent[i][0]][col + adjacent[i][1]] == 0) {
                        row = row + adjacent[i][0];
                        col = col + adjacent[i][1];
                        cnt++;
                        System.out.println(row + "  " + col + "  cnt = " + cnt);
                        move(cnt, row, col);
                    }
                }
            }
        }
        chess[row][col] = 0;
    }

    private static void initializeChess() {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                chess[i][j] = 0;
            }
        }
    }
}

Upvotes: 2

Views: 133

Answers (2)

David Conrad
David Conrad

Reputation: 16359

Your backtracking is not correct. By the time the last line executes, setting chess[row][col] back to zero, row and col have almost certainly changed.

It would be better to never change row, col, and cnt in your method, but only pass new values into the recursive call. Something like this, although I haven't checked the rest of your logic:

    for (int i = 0; i < 8; i++) {
        int nextrow = row + adjacent[i][0];
        int nextcol = col + adjacent[i][1];
        if (nextrow >= 0 && nextrow < 8 &&
                nextcol >= 0 && nextcol < 8) {
            if (chess[nextrow][nextcol] == 0) {
                System.out.println(nextrow + "  " + nextcol + "  cnt = " + (cnt+1));
                move(cnt+1, nextrow, nextcol);
            }
        }
    }

To ensure you're consistent in only modifying the values that are passed down to the subsequent recursive call, and never modifying them within the method, you can make the parameters final:

private static void move(final int cnt, final int row, final int col) {
    ...
}

Upvotes: 2

GhostCat
GhostCat

Reputation: 140427

A first problem is here:

for (int i = 0; i < 8; i++) {

So, you have that out for loop. Lets assume you enter with cnt at 51.

Now you have

if ( ... some overly complicated condition ... ) {
  ... cnt++
  move(cnt,

What happens now is: first you make your recursive calls, and probably each time right your first if hits. Thus, you increase cnt and recurse again. Therefore your printouts show how cnt is constantly increasing.

But at some point, the recursion ends - the if condition doesn't get true any more. So the recursively called method ... ends. But keep in mind: you called that method ... from another call to move. And that one might still be looping. And more importantly, that move() has its own version of cnt.

To see what I mean: change cnt from being a method local variable to be a field of your class, similar to your board! When you do that, you will find that your code actually prints:

...
3  7  cnt = 52
2  4  cnt = 53
...
2  3  cnt = 64
You moved around all cells: 64
0  4  cnt = 65
...

to actually stop later on with 

4  0  cnt = 126

Meaning: printing of cnt is just a side effect of your algorithm not really working correctly!

Finally: I would recommend to break up your if condition into a set of small helper methods, like

private static isXyz(...)

and to call those methods within that if statement - it would help with readability dramatically!

Upvotes: 2

Related Questions