Проблемы с пониманием этой функции рекурсии решателя судоку (python)

Question

Итак, в основном я решил сделать решатель судоку в python, и рекурсивные функции наиболее эффективны, но я пытался понять этот код на YouTube и не понимаю, почему каждый пробел (bo [row] [ col]) не сбрасывается сразу на 0. Сброс одного пробела на 0 происходит только в том случае, если решение (bo) равно True, но если я просматриваю код, плата вернет True, только если плата полностью решена, поэтому почему эта функция просто ни к чему не приведет, ведь решить (bo) никогда не будет True?

def solve(bo):
    find = find_empty(bo)

    if not find:
        return True  # This is the only time that solve(bo) == True
    else:
        row, col = find

    for i in range(1, 10):
        if valid(bo, i, (row, col)):
            bo[row][col] = i

            if solve(bo):
                return True

            bo[row][col] = 0   # Yet here it resets the space to 0 if solve(bo) is False

    return False


def valid(bo, num, pos):
    for i in range(9):
        if bo[pos[0]][i] == num and pos[1] != i:
            return False

    for i in range(9):
        if bo[i][pos[1]] == num and pos[0] != i:
            return False

    box_x = (pos[1] // 3) * 3
    box_y = (pos[0] // 3) * 3

    for i in range(box_y, box_y + 3):
        for j in range(box_x, box_x + 3):
            if bo[i][j] == num and (i, j) != pos:
                return False

    return True


def find_empty(bo):
    for y in range(9):
        for x in range(9):
            if bo[y][x] == 0:
                return (y, x)
    return False

Answer 1

Есть некоторое расхождение между вашим объяснением и комментариями в коде, но я все равно сделаю все возможное, чтобы объяснить код.

First resolve () попытается найти первое пустое место (то есть такое, которое равно 0). Если он не может найти ни одного, то плата решается, поэтому он возвращает истину.

Если он действительно находит место, то он попытается поместить туда числа 1-9 и проверить если работает с ранее введенными номерами. Скажем, 7 работает (мы не знаем, работают ли 8 или 9, потому что мы еще не проверили это). Итак, мы устанавливаем пустое пространство на 7 и затем передаем обновленную доску в рекурсивном вызове. По сути, это все равно что сказать: «Если я заставлю это место иметь число 7, сможете ли вы найти решение?»

Если рекурсивный вызов вернет истину, это означает, что есть решение с 7 в этом месте и следовательно, у платы есть решение, поэтому мы возвращаем true. Если рекурсивный вызов решения () возвращает false, то мы знаем, что для доски с 7 в этом месте нет решения, поэтому мы сбрасываем это место на 0, а затем пробуем 8 (а затем 9, если необходимо).

Следует помнить, что во всех рекурсивных вызовах есть только одна доска (bo) - другими словами, все вызовы функций работают с одной и той же переменной bo. Он не создает копию доски каждый раз, когда вы делаете рекурсивный вызов. Ищите «Передавать по ссылке» и «мелкие или глубокие копии», если хотите узнать больше о том, почему.