Рекурсия Python Sudoku с ошибкой возврата грубой силы

Проблема, с которой вы сталкиваетесь, заключается в том, что некоторые из ваших рекурсивных вызовов не возвращают результаты должным образом, поэтому ваше решение, когда оно найдено, забывается о нескольких уровнях рекурсивного стека. Вот первое необходимое вам исправление, добавляющее return к рекурсивным вызовам, сделанным в mover:

def mover(self, row, col):
    if col + 1 != 9:
        return self.solve_helper(row, (col+1))  # added return
    elif row + 1 != 9:
        print "Moving to row" + str(row + 1)
        return self.solve_helper((row+1),0)     # here too
    else:
        print "SOLUTION FOUND"
        return True

Вам также нужно что-то подобное в особом случае вашей функции solve_helper, когда вы пропускаете предварительно решенные ячейки. Конец функции должен быть:

else:
    return self.mover(row, col)  # added return
return False

Изменить:

Хорошо, я нашел еще несколько проблем в коде. Две из них — логические проблемы с решателем, а одна — проблема с отображением, которая не вызывает никаких реальных проблем, кроме странного внешнего вида во время решения.

Проблемы:

1. Во-первых, в вашем последнем коде solve_helper вызывает сам себя, а не mover. Это заставляет выполнять дополнительный вызов функции перед перемещением (хотя я думаю, что на самом деле это может не сломать решатель).
2. Во-вторых, если solve_helper устанавливает ячейку в 9, но затем при возврате к (после того, как некоторые более поздние ячейки не могут быть решены), 9 не сбрасывается до нуля перед дальнейшим возвратом.
3. И, наконец, проблема с дисплеем. Установка для ячеек значения 0 не останавливает отображение их старого значения. Это очень похоже на проблему в № 2 (с оставшимися девятками после возврата), но на самом деле это только косметический эффект.

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

Вторая проблема немного сложнее, и здесь вы застреваете на некоторых досках. Что вам нужно сделать, так это переместить строку, выполняющую self.set_cell(row, col, 0), из блока else, в котором она находится в данный момент. На самом деле, вы можете полностью переместить ее за пределы цикла, если хотите (поскольку это действительно необходимо только в том случае, если вы возврат после того, как ни одно из значений для текущей ячейки не сработало). Вот что я думаю, что это наилучшее расположение цикла for (также перемещение оператора return False вверх):

for i in range(1,10):
    print("Setting value ") + str (i) + (" at " ) + str(row) + ", " + str(col)
    self.set_cell(row, col, i)
    self.guesses = self.guesses + 1
    if self.check_cell(row, col):
        if self.mover(row, col):
            return True
print "Backtracking"
self.set_cell(row, col, 0)
return False

Наконец, исправление проблемы с отображением требует двух изменений. Во-первых, избавьтесь от условного оператора в set_cell. Вы хотите всегда обновлять дисплей. Затем в update_textfield переместите вызов delete за пределы блока if, чтобы он всегда происходил (оставьте insert под if). Это делает так, что установка ячейки на ноль удалит предыдущее значение, но не заставит ее отображать фактический символ 0 (она ничего не покажет).

Я думаю, что это должно сделать это. Обратите внимание, что используемый вами алгоритм все еще довольно медленный. Решение доски, которую я нашел в Интернете в результате быстрого поиска в Google, потребовало 122482 предположений и более 5 минут, но это, наконец, сработало. Другие доски (особенно те, которые требуют 8 или 9 в первых нескольких открытых местах) могут занять еще больше времени.