数独求解器 Python

Python 3月前 4

数独是一种基于逻辑的数字排列谜题游戏，在热爱逻辑和推理的人中最受欢迎。解决数独谜题有助于大脑提高注意力和逻辑思维。

本文介绍了我们如何使用Python解决数独问题。

在Python中使用回溯算法来解决数独问题

在寻找计算问题的解决方案时，回溯算法是我们经常使用的技术。在解数独时，它检查填入框中的数字是否有效。

如果是无效的，它就检查1到9的其他数字。如果它发现没有有效的数字，它就回溯到前一个选项。

当我们到达一个死胡同并返回到上一个选择时，我们已经做出并将改变我们的选择，从而产生一个不同的可能解决方案。

让我们采取与回溯算法一起实现数独解算器的方法。

首先，我们必须通过形成谜题来设置棋盘。

def setBoardFunc(puz):
    global grid
    print('n---------------Sudoku Solver---------------n')
    print('Here is the Sudoku Problem :')
    for i in range(0, len(puz), 9):
        row = puz[i:i+9]
        temp = []
        for block in row:
            temp.append(int(block))
        grid.append(temp)
    printGridFunc()

在这里，我定义了一个名为setBoardFunc() 的函数来形成谜题。在循环过程中，它设置了一个9×9的拼图，并将空单元格初始化为0 。

在完成函数的操作后，它打印出在puz 中给出的输入。然后我们要打印网格；这一步打印出9×9的网格，并给出输入。

def printGridFunc():
    global grid
    for row in grid:
        print(row)

接下来，我们将检查当前值是否能放在当前的方格内。

def checkValidFunc(row,column,num):
    global grid
    for i in range(0,9):
        if grid[row][i] == num:
            return False
    for i in range(0,9):
        if grid[i][column] == num:
            return False
    square_row = (row//3)*3
    square_col = (column//3)*3
    for i in range(0,3):
        for j in range(0,3):
            if grid[square_row+i][square_col+j] == num:
                return False
    return True

这一步检查给定的数字是否对特定的盒子有效。这个数字应该是同行、同列、同块的盒子中没有一个能放在当前位置的。

如果该数字满足该要求并返回true ，我们就可以转到下一个值；如果不是，该数字会被拒绝。然后我们要遍历所有的块，适应回溯算法。

def solveFunc():
    global grid
    for row in range(9):
        for column in range(9):
            if grid[row][column] == 0:
                for num in range(1,10):
                    if checkValidFunc(row,column,num):
                        grid[row][column] = num
                        solveFunc()
                        grid[row][column] = 0
                return
    print('nSolution for the Sudoku Problem: ')
    printGridFunc()

这个代码块的后半部分检查数字是否有效。在这里，它已经引入了函数回溯算法。

首先，它搜索一个空单元格；如果找到了，则说明已解的数独在那里，并打印出给定数独的解。如果它发现了任何空格，它将通过迭代猜测一个从1到9的数字。

如果存在一个有效的数字，它就会调用solveFunc() ，并移动到下一个空单元格，但是如果没有一个猜测的数字是有效的，那么之前调用的函数将把单元格的值重置为0 ，并继续迭代以找到下面的有效数字。

当算法用有效数字填满空框直到死胡同时，它就会回溯这个过程并重新重复整个过程。最后，让我们传递网格并调用函数来解决给定的数独问题。

puz = "004300209005009001070060043006002087190007400050083000600000105003508690042910300"
grid = []
setBoardFunc(puz)
solveFunc()

完整的源代码：

def setBoardFunc(puz):
    global grid
    print('n---------------Sudoku Solver---------------n')
    print('Here is the Sudoku Problem :')
    for i in range(0, len(puz), 9):
        row = puz[i:i+9]
        temp = []
        for block in row:
            temp.append(int(block))
        grid.append(temp)
    printGridFunc()
def printGridFunc():
    global grid
    for row in grid:
        print(row)
def checkValidFunc(row,column,num):
    global grid
    for i in range(0,9):
        if grid[row][i] == num:
            return False
    for i in range(0,9):
        if grid[i][column] == num:
            return False
    square_row = (row//3)*3
    square_col = (column//3)*3
    for i in range(0,3):
        for j in range(0,3):
            if grid[square_row+i][square_col+j] == num:
                return False
    return True
def solveFunc():
    global grid
    for row in range(9):
        for column in range(9):
            if grid[row][column] == 0:
                for num in range(1,10):
                    if checkValidFunc(row,column,num):
                        grid[row][column] = num
                        solveFunc()
                        grid[row][column] = 0
                return
    print('nSolution for the Sudoku Problem: ')
    printGridFunc()
puz = "004300209005009001070060043006002087190007400050083000600000105003508690042910300"
grid = []
setBoardFunc(puz)
solveFunc()