Это программа для решения судоку. Я получил рекурсивные ошибки. Я импортировал модуль sys и установил предел рекурсии 1500, но все равно он показывает ошибки - PullRequest
Новая
       57

Это программа для решения судоку. Я получил рекурсивные ошибки. Я импортировал модуль sys и установил предел рекурсии 1500, но все равно он показывает ошибки

0 голосов
/ 11 января 2020 
import sys
sys.setrecursionlimit(1500)  # the default recursion limit is 1000


def print_grid(arr):
    for i in range(9):
        for j in range(9):
            print(arr[i][j])
    print('\n')


def find_empty_location(arr, l):
    for i in range(9):
        for j in range(9):
            if (arr[i][j] == 0):
                l[0] = i
                l[1] = j
                return True

    return False


def row_check(arr, row, num):
    for x in range(9):
        if arr[row][x] == num:
            return True

    return False


def col_check(arr, col, num):
    for i in range(9):
        if arr[i][col] == num:
            return True

    return False


def used_in_box(arr, row, col, num):
    for i in range(3):
        for j in range(3):
            if (arr[i + row][j + col] == num):
                return True

    return False


def check_location_is_safe(arr, row, col, num):
    return not row_check(arr, row, num) and not col_check(arr, col, num) and not used_in_box(arr, row - row % 3, col - col % 3, num)


def solve_sudoku(arr):
    l = [0, 0]
    if (not find_empty_location(arr, l)):
        return True

    row = l[0]
    col = l[1]

    for num in range(1, 10):
        if check_location_is_safe(arr, row, col, num):
            arr[row][col] == num

        if solve_sudoku(arr):
            return True

        else:
            arr[row][col] = 0
            return False


if __name__ == "__main__":
    grid = [[0 for x in range(9)] for y in range(9)]

    grid = [[3, 0, 6, 5, 0, 8, 4, 0, 0],
            [5, 2, 0, 0, 0, 0, 0, 0, 0],
            [0, 8, 7, 0, 0, 0, 0, 3, 1],
            [0, 0, 3, 0, 1, 0, 0, 8, 0],
            [9, 0, 0, 8, 6, 3, 0, 0, 5],
            [0, 5, 0, 0, 9, 0, 6, 0, 0],
            [1, 3, 0, 0, 0, 0, 2, 5, 0],
            [0, 0, 0, 0, 0, 0, 0, 7, 4],
            [0, 0, 5, 2, 0, 6, 3, 0, 0]]
    if (solve_sudoku(grid)):
        print_grid(grid)

    else:
        print('NO SOLUTION EXISTS')

1 Ответ

0 голосов
/ 11 января 2020

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

Вместо этого вы должны отладить и посмотреть, что на самом деле происходит. В таких случаях я обычно добавляю параметр depth=0 в рекурсивную функцию (значение по умолчанию 0). Затем убедитесь, что рекурсивный вызов передает значение depth+1. Добавьте if depth > 5: raise ValueError("stop") в функцию, чтобы она не запускалась так часто. Наконец, добавьте несколько операторов print, чтобы проверить, как выглядит ваша сетка, какие строки / столбцы выбраны ... et c. Вскоре вы обнаружите, что что-то идет ужасно неправильно ...

Теперь к коду: в вашей функции solve_sudoku есть следующие проблемы:

  • arr[row][col] == num не является назначение, но сравнение. Таким образом, вы на самом деле никогда не меняете сетку.

  • Даже с учетом вышеприведенного исправления вы все равно продолжаете повторение без изменения сетки, когда check_location_is_safe возвращает False. Таким образом, следующие строки должны были иметь больше отступов, чтобы они принадлежали блоку if над ним: 

    if solve_sudoku(arr):
     return True
else:
     arr[row][col] = 0
     # return False <--- not here (cf. previous issue)

    Примечание: поскольку в случае if вы выходите из функции, на самом деле нет реального нужно иметь arr[row][col] = 0 в else. Так что вполне может быть: 

    if solve_sudoku(arr):
     return True
arr[row][col] = 0
  • return False не должно быть внутри for l oop, потому что вы все еще хотите проверить альтернативные «ходы» в следующих итерациях l oop. return False должно быть выполнено после того, как l oop закончится.

Итак, взяв эти исправления вместе: вторая половина solve_sudoku должна выглядеть следующим образом: 

for num in range(1, 10):
    if check_location_is_safe(arr, row, col, num):
        arr[row][col] = num
        if solve_sudoku(arr):
            return True
        arr[row][col] = 0
return False
...