CODEWITHSUNDEEP
javarecursionbacktracking
Ama
Ama

Reputation: 21

Sudoku solver with recursion and backtracking

I'm trying to code a sudoku solver with recursion and backtracking. But there are some problems with my code it always return false. I tried to debug, it calls next(int row, int col) method up to second row, sixth column and then it stops and backtracking starts. The problem is that the backtracking continues till first cell in my sudoku game and then it returns false. It doesnt replace the cell numbers with others.

here is my code... have I missed anything?

/** Calls solve for the next cell */
private boolean next(int row, int col) {
    if (col < 8)
        return solve(row, col + 1);
    else
        return solve(row + 1, 0);
}

public boolean solve(int row, int col) {
    if (row > 8) {
        return true;
    }
    if (model[row][col] != 0) {
        if (isSafe(row, col, model[row][col]))
            return next(row, col);
    }
    for (int value = 1; value < 10; value++) {
        if (isSafe(row, col, value)) {
            model[row][col] = value;
            return next(row, col);
        }
    }
    return false;
}

Upvotes: 2

Views: 293

Answers (2)

Joop Eggen
Joop Eggen

Reputation: 109547

return next(row, col);

should be

if (next(row, col)) {
    return true;
}

And the if with == 0 seems to have no purpose.

All done

Untested but with correct back-tracking: setting the cell again to 0, so it can be filled in again.

public boolean solve(int row, int col) {
    if (row > 8) {
        return true;
    }
    if (model[row][col] != 0) {
        // isSafe may be assumed on correct puzzles.
        return isSafe(row, col, model[row][col]))
            && next(row, col);
    }

    for (int value = 1; value < 10; value++) {
        if (isSafe(row, col, value)) {
            model[row][col] = value;
            if (next(row, col)) {
                return true;
            }
        }
    }
    model[row][col] = 0;
    return false;
}

Upvotes: 1

gyurix
gyurix

Reputation: 1086

Try to add model[row][col] = 0; before the return false;

Upvotes: 1

Related Questions