Почему мой алгоритм отслеживания не работает и выдает квадраты с дублированными записями?

Question

Привет! Я пытаюсь использовать возврат для решения Головоломки Судоку .

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

def findBlank(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return (i,j)
    return False

def feasibleMove(board, coordinate, number):
    x, y = coordinate
    #check row
    for i in range(9):
        if board[x][i] == number and y != i:
            return False
    #check column
    for i in range(9):
        if board[i][y] == number and x != i:
            return False
    #check box
    row = coordinate[0] // 3
    col = coordinate[1] // 3

    for i in range(x * 3, x * 3 + 3):
        for j in range(y * 3, y * 3 + 3):
            if board[row][col] == number and (i, j) != coordinate:
                return False

    return True

def solver(board):
    blankCell = findBlank(board)
    if not blankCell:
        return True
    else:
        row, col = blankCell

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

            if solver(board):
                return True

            board[row][col] = 0

    return False

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

С доской, предоставленной, когда Я запускаю алгоритм, который я получаю:

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

Кажется, он работает для столбца за столбцом и строки за строкой. Однако квадраты 3x3 неверны.

Например, берется верхний левый квадрат

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

Здесь есть дублированные записи, например 3, и также не содержится каждое число 1-9 точно один раз.

Основываясь на моем методе feasibleMove, это не должно быть разрешено!

Очевидно, что я допустил ошибку, но не вижу, где ...

Любой идеи?

Answer 1

Причина в том, что в этой части feasibleMove есть ошибки:

row = coordinate[0] // 3
col = coordinate[1] // 3

for i in range(x * 3, x * 3 + 3):
    for j in range(y * 3, y * 3 + 3):
        if board[row][col] == number and (i, j) != coordinate:
            return False

Итерация должна основываться на row и col, а не на x и y. И когда вы считываете значение из board, вы должны использовать i и j в качестве индексов. Прямо сейчас вы 9 раз смотрите на одну и ту же ячейку на своей доске.

row = (x // 3) * 3
col = (y // 3) * 3

for i in range(row, row + 3):
    for j in range(col, col + 3):
        if board[i][j] == number and (i, j) != coordinate:
            return False

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

• Не ищите пустые ячейки в реальном времени. Вместо этого соберите их в очередь и вытолкните оттуда (и верните их обратно при обратном отслеживании)
• Вместо проверки допустимости значения для ячейки, оставайтесь на шаг впереди и следите за тем, какие значения все еще действительны (в set) для каждой ячейки. Инициализируйте это в самом начале алгоритма.
• При размещении значения обновляйте наборы затронутых ячеек

Эти последние две точки могут показаться бесполезными, поскольку он просто сдвигает работа сканирования строк, столбцов и полей в другой момент в алгоритме, но выгода здесь:

• Для того, чтобы сохранить рекурсивное дерево узким, отдавайте приоритет ячейкам, у которых осталось наименьшее количество возможных значений В идеале только один. Для этого вы можете использовать python heapq, и его следует применить к очереди, о которой я упоминал в первом пункте.

Я оставляю реализацию для вас, так как она не была ваш вопрос. В любом случае, на net есть множество рабочих примеров.