Я делаю SudokuSolver для класса, и у меня возникли проблемы с методом решения. Мое текущее решение использует рекурсивный поиск с возвратом (, я думаю ).

Требования к назначению

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

(Описанная выше стратегия)

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.

Идея псевдокода

Я могу следовать этому итеративно для небольшого ввода. Например, скажем, у меня есть нерешенные ячейки Cell #1 и Cell #2. #1 имеет возможности { 1, 3 }, а #2 имеет возможности { 2, 3 }. Я бы тогда

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

Фактический код

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

    if (!hasConflicts()) {
        Queue 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 unsolved) {
    if (unsolved.isEmpty()) {
        return (hasConflicts()) ? 0 : 1;
    }

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

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

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

    return result + solveRec(unsolved);
}

Результаты испытаний

testSolveSingleSolution
    expected 1, actual 1

testSolveSolved
    expected 1, actual 1

testSolveUnsolvable
    expected 0, actual 0

testSolveMultiSolutions
    expected 2, actual 7  // MAJOR PROBLEM!

Несколько хороших объяснений рекурсивного поиска с возвратом

• Этот ответ на StackOverflow -Рекурсивное решение генератора судоку
• Этот ответ на StackOverflow -BackTracking в лабиринте
• Этот ответ на StackOverflow -Алгоритм возврата для простой последовательности
• Этот ответ на StackOverflow -Как найти первое решение только с этим возвратом
• Статья в Википедии о возврате
• Объяснение рекурсивного поиска с возвратом

Вопрос

Я делал рекурсивный возврат раньше, я просмотрел все эти ссылки выше и многое другое, и у меня все еще есть проблемы. Я думаю, что проблема заключается в моих размышлениях о том, как решить эту проблему. (См. Идея псевдокода. )Уместно ли использовать рекурсивный поиск с возвратом для полного поиска? Является ли откат правильным, но неверным реализация? Есть ли лучший алгоритм, который я могу использовать, чем рекурсивный возврат?