Как улучшить этот Судоку Солвер?

Question

Некоторое время назад у меня была идея создать программу, которая решала бы судоку, поэтому я сделал код ниже. Код получает в качестве входных данных список целых чисел 9x9, где неполная ячейка представлена ​​числом 0.

def checkSolutions(grid, i, j):
    """
    Given a Sudoku board and the position of an
    incomplete cell, it returns a list with all
    the possible numbers that this position can occupy.
    """

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

    solutions1x9 = [grid[x][j] for x in range(9)]
    solutions9x1 = [grid[i][x] for x in range(9)]

    rowGrid = i // 3
    columnGrid = j // 3
    solutions3x3 = [grid[i][j] for i in range(3*rowGrid, 3*rowGrid+3)
                    for j in range(3*columnGrid, 3*columnGrid+3)]

    solutions = solutions + [i for i in digits if i not in solutions1x9]
    solutions = solutions + [i for i in digits if i not in solutions9x1]
    solutions = solutions + [i for i in digits if i not in solutions3x3]

    solutions = list(set(solutions))
    solutions = [i for i in solutions if i not in solutions1x9]
    solutions = [i for i in solutions if i not in solutions9x1]
    solutions = [i for i in solutions if i not in solutions3x3]

    return solutions

def checkSudoku(grid):
    """
    Given a Sudoku board, it returns True if it is
    a board that follows the rules of the game and
    returns False otherwise.
    """

    digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    for i in range(9):
        if sorted(grid[i]) != digits:
            return False

    for i in range(9):
        column = [grid[j][i] for j in range(9)]
        if sorted(column) != digits:
            return False

    for i in range(3):
        for j in range(3):
            grid3x3 = [grid[x][y] for x in range(3*i, 3*i+3)
                    for y in range(3*j, 3*j+3)]
            if sorted(grid3x3) != digits:
                return False

    return True

def sudoku(grid):
    """
    Given an incomplete Sudoku board, it prints on
    the screen the solution of that game.
    """
    for i in range(9):
        for j in range(9):
            if grid[i][j] == 0:
                solutions = checkSolutions(grid, i, j)

                if len(solutions) == 1:
                    grid[i][j] = solutions[0]
                    continue

                for k in solutions:
                    auxGrid = [x.copy() for x in grid]
                    auxGrid[i][j] = k
                    sudoku(auxGrid)

    if checkSudoku(grid):
        print(grid)

Моя проблема: если функция sudoku получает в качестве входных данных следующий список

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

возвращает результат менее чем за одну секунду, то есть

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

Но если он получает в качестве входных данных список:

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

должно вернуть

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

но программа запускается так долго, что я даже не знаю, возвращает ли она что-то (я подождал 30 минут, прежде чем завершить выполнение кода). Итак, мои сомнения:

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

Спасибо за любую помощь!

Answer 1

Вы можете заставить свою программу решить вторую загадку, добавив оператор return к функции sudoku() в конце вложенных циклов.В приведенном ниже коде есть это исправление и некоторые другие идеи для доработки:

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

def checkSolutions(grid, i, j):
    """
    Given a Sudoku board, and the position of an
    incomplete cell, it returns a list with all
    the possible numbers that can occupy this position.
    """

    solutions1x9 = [grid[x][j] for x in range(9)]
    solutions9x1 = [grid[i][x] for x in range(9)]

    rowGrid = 3 * (i // 3)
    columnGrid = 3 * (j // 3)
    solutions3x3 = [grid[i][j] for i in range(rowGrid, rowGrid + 3) for j in range(columnGrid, columnGrid + 3)]

    return [digit for digit in DIGITS if digit not in solutions1x9 and digit not in solutions9x1 and digit not in solutions3x3]

def checkSudoku(grid):
    """
    Given a Sudoku board, it returns True if it is
    a board that follows the rules of the game and
    returns False otherwise.
    """

    for i in range(9):
        if sorted(grid[i]) != DIGITS:
            return False

    for j in range(9):
        column = [grid[i][j] for i in range(9)]

        if sorted(column) != DIGITS:
            return False

    for i in range(3):
        for j in range(3):
            grid3x3 = [grid[x][y] for x in range(3 * i, 3 * i + 3) for y in range(3 * j, 3 * j + 3)]

            if sorted(grid3x3) != DIGITS:
                return False
    return True

def sudoku(grid):
    """
    Given an incomplete Sudoku board, it prints on
    the screen the solution of that game.
    """

    for i in range(9):
        for j in range(9):
            if grid[i][j] == 0:
                solutions = checkSolutions(grid, i, j)

                if len(solutions) == 1:
                    grid[i][j] = solutions[0]  # permanent change to *this* reality
                    continue

                for k in solutions:
                    auxGrid = [x.copy() for x in grid]  # spawn a new reality
                    auxGrid[i][j] = k
                    sudoku(auxGrid)

                return  # already solved it recursively or no solution in *this* reality

    if checkSudoku(grid):
        print(grid)

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

sudoku(grid2)

ВЫХОД

> python3 test.py
[[1, 6, 8, 4, 5, 7, 9, 3, 2],
 [5, 7, 2, 3, 9, 1, 4, 6, 8],
 [9, 3, 4, 6, 2, 8, 5, 1, 7],
 [8, 2, 9, 7, 4, 3, 1, 5, 6],
 [6, 5, 1, 2, 8, 9, 3, 7, 4],
 [7, 4, 3, 5, 1, 6, 2, 8, 9],
 [3, 9, 5, 8, 7, 2, 6, 4, 1],
 [4, 1, 7, 9, 6, 5, 8, 2, 3],
 [2, 8, 6, 1, 3, 4, 7, 9, 5]]
>

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

Сделанная мною модификация может помешать вашему коду найти несколько решений, если они существуют.

Answer 2

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

def sudoku(grid):
    sudoku_dict = {}
    r = 'ABCDEFGHI'
    c = '123456789'
    for i in range(9):
        for j in range(9):
            sudoku_dict[r[i]+c[j]] = str(grid[i][j]) if grid[i][j] != 0 else c
    square = [[x+y for x in i for y in j] for i in ('ABC','DEF','GHI') for j in ('123','456','789')]
    peers = {}
    for key in sudoku_dict.keys():
        value = [i for i in square if key in i][0]
        row = [[x+y for x in i for y in j][0] for i in key[0] for j in c]
        col = [[x+y for x in i for y in j][0] for i in r for j in key[1]]
        peers[key] = set(x for x in value+row+col if x != key)
    for i in range(9):
        sudoku_dict = Check(sudoku_dict,peers)
    sudoku_dict = search(sudoku_dict, peers)
    solution = []
    for i in r:
        solution.append([])
        for j in c:
            solution[r.find(i)].append(int(sudoku_dict[i+j]))
    return solution

def Check(sudoku_dict, peers):
    for k,v in sudoku_dict.items():
        if len(v) == 1:
            for s in peers[k]:
                sudoku_dict[s] = sudoku_dict[s].replace(v,'')
                if len(sudoku_dict[s])==0:
                    return False
    return sudoku_dict

def search(sudoku_dict,peers):
    if Check(sudoku_dict,peers)==False:
        return False
    if all(len(sudoku_dict[s]) == 1 for s in sudoku_dict.keys()): 
        return sudoku_dict
    n,s = min((len(sudoku_dict[s]), s) for s in sudoku_dict.keys() if len(sudoku_dict[s]) > 1)
    res = []
    for value in sudoku_dict[s]:
        new_sudoku_dict = sudoku_dict.copy()
        new_sudoku_dict[s] = value
        ans = search(new_sudoku_dict, peers)
        if ans:
            res.append(ans)
    if len(res) > 1:
        raise Exception("Error")
    elif len(res) == 1:
        return res[0]