When is recursive backtracking appropriate?

Question

I'm making a SudokuSolver for a class, and I'm having trouble with the solve method. My current solution uses recursive backtracking (I think).

Assignment Requirements

int solve() -- tries to solve the puzzle using the strategy described above. Returns the number of solutions.

(The strategy described above)

When assigning a number to a spot, never assign a number that, at that moment, conflicts with the spot's row, column, or square. We are up-front careful about assigning legal numbers to a spot, rather than assigning any number 1..9 and finding the problem later in the recursion. Assume that the initial grid is all legal, and make only legal spot assignments thereafter.

Pseudocode Idea

I can follow this iteratively for a small input. For example, say I have to unsolved cells Cell #1 and Cell #2. #1 has possibilities { 1, 3 } and #2 has possibilities { 2, 3 }. I would then

set 1 to 1
    set 2 to 2
        hasConflicts? 0 : 1
    set 2 to 3
        hasConflicts? 0 : 1
set 1 to 3
    set 2 to 2
        hasConflicts? 0 : 1
    set 2 to 3
        hasConflicts? 0 : 1

Actual Code

public int solve() {
    long startTime = System.currentTimeMillis();
    int result = 0;

    if (!hasConflicts()) {
        Queue<VariableCell> unsolved = getUnsolved();
        reduceUnsolvedPossibilities(unsolved);  // Gets the possibilities down from all of 1-9

        if (!hasConflicts()) {
            result = solveRec(unsolved);
        }
    }

    mElapsedTime = System.currentTimeMillis() - startTime;
    return result;
}

protected int solveRec(Queue<VariableCell> unsolved) {
    if (unsolved.isEmpty()) {
        return (hasConflicts()) ? 0 : 1;
    }

    int result = 0;
    VariableCell cell = unsolved.remove();
    Iterator<String> possibilityIt = cell.getPossibilities().iterator();

    while (possibilityIt.hasNext()) {
        cell.setSymbol(possibilityIt.next());

        if (hasConflicts()) {
            possibilityIt.remove();
        } else {
            ++result;
        }
    }

    return result + solveRec(unsolved);
}

Test Results

testSolveSingleSolution
    expected 1, actual 1

testSolveSolved
    expected 1, actual 1

testSolveUnsolvable
    expected 0, actual 0

testSolveMultiSolutions
    expected 2, actual 7  // MAJOR PROBLEM!

Some Good Explanations of Recursive Backtracking

This answer to StackOverflow - Recursive solution to Sudoku generator
This answer to StackOverflow - BackTracking in a maze
This answer to StackOverflow - Backtracking algorithm for prime sequence
This answer to StackOverflow - How to find the first solution only with this backtracking
The Wikipedia article on Backtracking
Recursive Backtracking Explanation

Question

I've done recursive backtracking before, I've looked at all those links above and more, and I'm still having trouble. I think the problem lies in my thinking about how to solve this. (See Pseudocode Idea.) Is it appropriate to use recursive backtracking for an exhaustive search? Is the backtracking right but the implementation wrong? Is there a better algorithm I can use than recursive backtracking?

Backtracking is a reasonable approach if you can prune your search. — nikhil, Jul 17 '12 at 16:38
@nikhil Does the pruning need to happen during the recursion? — Eva, Jul 17 '12 at 16:42
It's an integral part, but the only thing it does is help with performance (and you basically have to search the whole tree in the worst case to find the right solution; contrary to adversial games where you don't necessarily need the "best" possible move, just the best move you can find in a given timeslot). Only allowing valid moves is already a kind of pruning. Anyhow if you get the wrong result that's not the reason (except if you have a bug in there). [Possible algorithms to solve it](http://en.wikipedia.org/wiki/Algorithmics_of_sudoku). — Voo, Jul 17 '12 at 16:51
cont. Solving it with [exact cover](http://en.wikipedia.org/wiki/Exact_cover#Sudoku) is quite fun and you learn more than with the bruteforce recursive solution, so you may want to look into that - it also solves 9x9 puzzles of any kind instantly (that said even the worst case sudokus can be solved in seconds with a well written bruteforce approach). — Voo, Jul 17 '12 at 16:58
@Voo Thanks for the links. Unfortunately, I'm way too dumb to understand them in the slightest. — Eva, Jul 20 '12 at 23:08
@Voo I got really curious about exact cover, so I hunted down an explanation in plainer English. [Here's](http://gieseanw.wordpress.com/2011/06/16/solving-sudoku-revisited/) the link. I actually got a working version going! — Eva, Jul 22 '12 at 19:35
@Eva Nice link - while the set theory explanation has the advantage if being quite succinct and exact, I can see why some people would prefer a more extensive description. And whoever wrote that article explained the problem really well. Good to hear that you've got a working solution and at the same time learned an extremely useful new concept. — Voo, Jul 22 '12 at 21:32

score 1 · Accepted Answer · answered Jul 17 '12 at 16:49

1

This looks like an implementation problem. Check the block where you're incrementing result. Do you really want to increment for each valid value of that cell? And for that matter overwrite the older valid value if there are several that are valid?

answered Jul 17 '12 at 16:49

Thomas

5,074
1
16
12

I see what you mean about incrementing the value. It increments too much, and that should only be done once a valid solution has been found. I'm not sure what you mean by not overwriting the older value. I'm trying to check for a valid solution with that value before moving on to the next value. I think I might be doing that part wrong too. – Eva Jul 20 '12 at 23:39
Look carefully at the `while (possibilityIt.hasNext())` loop with particular attention to where you set the symbol as compared to where you make your recursive `solveRec` call. – Thomas Jul 21 '12 at 14:50