Java – when does recursive backtracking apply?

I'm creating a sudokusolver for a class, and I'm having trouble solving it My current solution uses recursive backtracking (I think)

Operation requirements

(above strategy)

Psychological thought

I can iteratively follow a small input For example, say I have to open cells #1 and cells #2# 1 possible {1,3} and #2 possible {2,3} I will

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);
}

detection result

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 for recursive backtracking

>This answer to stackoverflow – recursive solution of Sudoku generator > this answer to stackoverflow – backtracking in maze > this answer to stackoverflow – backtracking algorithm of main sequence > this answer to stackoverflow – how to find the first solution only this backtracking > Wikipedia article backtracking > recursive backtracking explanation

topic

I've done recursive backtracking before. I've seen all the links above. I'm still in trouble I think the problem is how I solve it (see psudeocode idea.) Is recursive backtracking suitable for exhaustive search? Is the retroactive right correctly implemented? Can I use a better algorithm than recursive backtracking? Thank you first!

Solution

This looks like an implementation problem The result of the check block increases Do you really want to increase each valid value of that cell? If there are several valid values, what about overwriting the old valid values?