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

Требования к присваиванию

int solve() - пытается решить головоломку, используя описанную выше стратегию. Возвращает количество решений.

(Стратегия, описанная выше)

При назначении номера пятну никогда не присваивайте номер, который в данный момент конфликтует с точечной строкой, столбцом или квадратом. Мы внимательно следим за назначением юридических чисел на место, вместо того, чтобы назначать любое число 1..9 и находить проблему позже в рекурсии. Предположим, что начальная сетка является законной и после этого совершает только юридические назначения.

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

Я могу следовать этому итеративно для небольшого ввода. Например, скажу, что у меня есть нерешенные ячейки 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<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);
}

Результаты тестирования

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 - как найти первое решение только с этим обратным трассированием
• Статья в Википедии о Backtracking
• Рекурсивное обратное отслеживание Пояснение

Вопрос

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