Как работает рекурсия в Sudoku Solver Algorithm?

Question

Пытался понять как это работает и возник вопрос с одним фрагментом кода, увидел данный алгоритм в одном из видео на Youtube канале Computerphile.

Код:

import numpy as np

grid = [[0, 0, 6, 0, 0, 0, 7, 0, 4],
        [0, 0, 0, 0, 0, 4, 0, 0, 0],
        [0, 0, 4, 9, 0, 2, 6, 8, 0],
        [0, 0, 7, 0, 4, 0, 0, 0 ,0],
        [3, 0, 0, 8, 0, 7, 0, 2, 0],
        [0, 0, 2, 0, 9, 0, 0, 0, 3],
        [0, 0, 5, 0, 7, 0, 0, 4, 0],
        [2, 0, 0, 0, 0, 0, 0, 1, 7],
        [6, 0, 0, 0, 0, 0, 0, 9, 5]]

def possible(arr, x, y, n):
    for i in range(0, 9):
        if grid[x][i] == n:
            return False
    for i in range(0, 9):
        if grid[i][y] == n:
            return False
    x0 = (x // 3) * 3
    y0 = (y // 3) * 3
    for i in range(0, 3):
        for j in range(0, 3):
            if grid[x0 + i][y0 + j] == n:
                return False
    return True

def solve(arr):
    for x in range(9):
        for y in range(9):
            if arr[x][y] == 0:
                for n in range(1, 10):
                    if possible(arr, x, y, n):
                        arr[x][y] = n
                        solve(arr)
                        arr[x][y] = 0
                return
    print(np.matrix(arr))

solve(grid)

Мне так и не ясно, что происходит в данной строке. Также, в другом блоке, по условию выше, сразу после цикла, имеется оператор return, что тоже вызывает у меня вопрос: для чего он там? Буду благодарен, если кто-нибудь объяснит, что эти строчки кода делают, и для чего они нужны.

                arr[x][y] = n
                solve(arr)
                arr[x][y] = 0

Answer 1

Этот блок кода изменяет ячейку массива, делает рекурсивный вызов, так что во всех нижележащих ветвях ячейка заполнена, потом возвращает массив в исходное состояние, делая ячейку пустой. Таким образом, деревья заполнения начинаются с разных первых заполненных ячеек.

Про return вопрос непонятен.

Answer 2

def solve(arr):
    # Список arr содержит 81 ячейку, 9 строк, 9 столбцов. В цикле
    # перебираем каждую ячейку
    for x in range(9):
        for y in range(9):
            # И проверяем, пуста ли она
            if arr[x][y] == 0:
                # Если данная ячейка пуста, пробуем поставить в неё числа
                # от 1 до 9. Число считается подходящим, когда функция
                # possible(arr, x, y, n) возвращает True.
                for n in range(1, 10):
                    # Если подходящее число найдено
                    if possible(arr, x, y, n):
                        # то записываем его в список arr
                        arr[x][y] = n
                        # и вызываем функцию solve(arr) ещё раз
                        # этот вызов функции solve() отличается от предыдущего тем,
                        # что в списке arr стало на одну заполненную ячейку больше.
                        ## Если число n было выбрано удачно, то последующие вызовы solve(arr)
                        # приведут к решению, если выбранное число n впоследствии привело в тупик,
                        # значит ему не место в этой ячейке и нужно вернуть ячейке значение '0'.
                        solve(arr)
                        # Это строчка выполняется когда цепочка вызовов
                        # solve(arr) достигает "дна" (см. Deep First Recursion) и при этом
                        # решение до сих пор не найдено.
                        ## Достигает "дна" означает, что внутри предыдущего вызова
                        # solve(arr) сработал return вместо очередного вызова функции
                        # solve(arr)
                        ## А раз решение не найдено, значит n, которое мы добавили
                        # в arr две строки назад (arr[x][y] = n) привело в тупик - 
                        # отменяем его.
                        arr[x][y] = 0
                # Здесь мы можем оказаться только в случае arr[x][y] == 0,
                # другими словами, если в списке arr остались пустые ячейки.
                # Когда пустых ячейк не останется, мы не попадём в этот блок if
                # и соответственно данный return не сработает.
                return
    # До этой строки дойдём только когда список arr заполнен целиком - решение найдено,
    # все остальные вызовы функции solve() будут заканчиваться на предыдущей строке
    # с "return"                
    print(np.matrix(arr))

БЛОГ НА HUSL

Как работает рекурсия в Sudoku Solver Algorithm?

Ответы (2 шт):