Откат судоку только вид работ в Python 3

Question

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

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

    [0, 0, 5,   0, 3, 0,  1, 0, 0],
    [0, 7, 0,   5, 0, 1,  0, 3, 0],
    [0, 0, 3,   0, 9, 0,  8, 0, 0],

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

def p(board):
    for i in board:
        print(i)

def find(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                return row, col
    return 1

def check_horizontal(board, row, number):
    for i in range(0, 9):
        if board[row][i] == number:
            return False
    return True

def check_vertical(board, col, number):
    for i in range(0, 9):
        if board[i][col] == number:
            return False
    return True

def check_sqaure(board, row, col, number):
    a = int(row / 3)
    b = int(col / 3)
    for i in range(a * 3, a * 3 + 3):
        for j in range(b * 3, b * 3 + 3):
            if board[i][j] == number:
                return False
    return True

def check_all(board, row, col, number):
    if check_horizontal(board, row, number) and check_vertical(board, col, number) and check_sqaure(board, row, col,number):
        return True

def play(board):
    if find(board) == 1:
        return 1
    row, col = find(board)
    for i in range(1, 10):
        if check_all(board, row, col, i):
            board[row][col] = i
            if play(board) == 1:
                return board
            else:
                if check_all(board, row, col,board[row][col] + 1):
                    board[row][col] = board[row][col] + 1   
play(board)
p(board)

, и это вывод:

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

Правильный результат будет:

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

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

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

Answer 1

Я вижу пару проблем с вашей play функцией.

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

else:
    if check_all(board, row, col,board[row][col] + 1):
        board[row][col] = board[row][col] + 1  

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

board[row][col] = 0

Другая проблема заключается в том, что у вас есть некоторые смешанные логики c о том, какое возвращаемое значение должно быть из play. В базовом случае вы возвращаете значение часового 1, и ваш более поздний рекурсивный код проверяет это. Но более поздний код вернет board вместо значения часового, если он думает, что получил решение из рекурсии. Вам нужно выбрать один из них и быть в соответствии с ним! Другая сторона этого заключается в том, что вы полагаетесь на возвращаемое по умолчанию значение None, чтобы указать на ошибку, когда вы падаете с конца функции. Вероятно, вы должны явно указать это возвращаемое значение, добавив return None.

Вот как я это сделаю, вернув доску:

def play(board):
    if find(board) == 1:
        return board            # first change, return the board here!
    row, col = find(board)
    for i in range(1, 10):
        if check_all(board, row, col, i):
            board[row][col] = i
            if play(board) is not None: # second change, check for a non-None value, not == 1
                return board
    board[row][col] = 0         # third change, do proper backtracking (replaced three lines)
    return None                 # fourth change, be explicit about our return value on failure

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

coords = find(board)
if coords == 1:
    return board
row, col = coords

Я бы также предпочел использовать None в качестве стража для неудачного find, но это больше вопрос вкуса, чем что-либо действительно неправильно или неэффективно.