Алгоритм поиска с возвратом в Python для решения судоку

Я недавно вернулся к написанию python и решил заняться проектом написания алгоритма обратного отслеживания на python для решения головоломок судоку.

Как это устроено

Объявлена ​​матрица, представляющая сетку судоку, пустые места в сетке судоку представлены нулем.Объявлена ​​функция, которая проверяет все нули в сетке, объявлена ​​другая функция для проверки правильности ответов путем проверки по переменной. объявлен как Row_Values он также проверяет переменную, объявленную как column_values затем объявляется другая функция, которая вызывает первую функцию, чтобы определить, где она может предположить, что она не возвращает ничего, если все пробелы заполнены, она вводит число от 1 до 9 в допустимом месте, а затем проверяет, не конфликтует ли она, затем использует рекурсия для вызова функции, которую он неоднократно проверяет, если что-то недопустимое, если оно становится недопустимым, использует обратное отслеживание, чтобы попробовать новый номер (а), возвращает false, если головоломка недействительна

Код

import numpy as np
import time

start_time = time.time()

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

print (np.matrix(grid))

def find_empty_box(sudoku): 
    for x in range(9):
        for y in range(9):
            if sudoku[x][y] == 0:
                return x, y 
    
    return None, None

def Answer_Valid(sudoku, guess, row, col): 
    row_values = sudoku[row]    
    if guess in row_values:
        return False

    column_values = [sudoku[i][col]for i in range(9)]
    if guess in column_values:
        return False

    row_start = (row // 3) * 3
    col_start = (col // 3) * 3 

    for x in range(row_start, row_start + 3):
        for y in range(col_start, col_start + 3):
            if sudoku[x][y] == guess:
                return False

        return True

def Solver(sudoku):
    row, col = find_empty_box(sudoku)

    if row is None:
        return True

    for guess in range(1,10):
        if Answer_Valid(sudoku, guess, row, col):
            sudoku[row][col] = guess

            if Solver(sudoku):
                return True

        sudoku[row][col] = 0

    return False

print(Solver(grid))

print(np.matrix(grid))

print("%s seconds " % (time.time() - start_time))

Ошибка в Answer_Valid

for x in range(row_start, row_start + 3):
    for y in range(col_start, col_start + 3):
        if sudoku[x][y] == guess:
            return False

    return True

он отлично работает, когда я запускаю его на своем компьютере

Так ли это на самом деле? Нет никаких сомнений в том, что он будет работать. Последствия этой ошибки заключаются не в том, что «не работает», а в том, что они дают плохие результаты. Основное следствие состоит в том, что True будет возвращен слишком рано, без проверки всего блока 3×3. Это может привести к неверным решениям. Программа все равно будет работать, но сделает неправильно. И, конечно же, программа может дать правильное решение, если ей повезет, поэтому получение правильных решений не означает, что проблем нет.

Нетрадиционное использование x и y

С использованием x индексировать строки и y Индексирование столбцов переносится по сравнению с обычным порядком. Это означает, что x увеличивается вниз, и y увеличивается через. Это странно и сбивает с толку, сначала я думал, что из-за этого было много ошибок, но похоже, что их нет. Эту проблему все еще стоит решить: код, который выглядит неправильно даже если это не так, это все равно нехорошо.

Общепринятые значения x и y приведет к тому, что выражения индексации будут выглядеть как sudoku[y][x] что выглядит странно, использование двумерного массива numpy позволит обеспечить правильную двумерную индексацию. Кстати, matrix следует избегать в соответствии с его документация, предпочитаю использовать 2D-массив.

Алгоритмические методы можно улучшить

Сетка, которую вы использовали в качестве примера, решается за разумное время, но есть сетки, которые вызывают проблемы. Например:

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

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

1. Обрабатывайте тривиальные ячейки, не дожидаясь, пока их «выберут», чтобы отгадать. Если в ячейке осталось только одно возможное значение (также известное как Naked Single), просто заполните его (но будьте осторожны, чтобы очистить их снова при возврате).
2. Посмотрите на загадку с точки зрения «где в этом ряду я мог бы поставить пятерку». Если есть только одно место, куда он может попасть (он же Скрытый сингл), он должен будет пойти туда, чтобы вы могли заполнить ячейку. Методы 1 и 2 можно повторять вместе, пока они не перестанут находить ячейки для заполнения. Я попытался добавить это в ваш решатель, и это сделало его достаточно мощным, чтобы решить примерную сетку, которую я показал.
3. (более продвинутый) Выберите пустую ячейку, чтобы угадать, основываясь на количестве оставшихся возможностей, а не просто на первой. Сначала нужно сделать ячейки с небольшим доменом. Это приводит к тому, что конфликты возникают раньше, что в разы лучше при возврате. Этот вид включает в себя первую технику (ячейки, в которых осталась только одна возможность, выбираются одна за другой и заполняются единственно возможной «догадкой»), но все же имеет смысл разбить это на отдельную вещь.

Вот несколько комментариев в произвольном порядке:

• Чтобы узнать время, затраченное на решение судоку, теперь вы учитываете время, затраченное на объявление используемых функций, и время, затраченное на печать в стандартном формате. Вероятно, это не предназначено.

• Согласно PEP-8, имена функций должны быть записаны как answer_valid и solver.

• Ваши входные данные не проходят проверки. Например, все должно быть хорошо, но если вы собираетесь предположить, что ваша судоку всегда 9×9, вы должны хотя бы проверить это и поднять ValueError.