Python 数独求解器

文章目录

- 使用回溯算法在Python中解决数独
- 总结

Sudoku（数独）是一种基于逻辑的数字填充谜题游戏，最受喜爱的是那些热爱逻辑和推理的人。解决数独谜题有助于提高集中注意力和逻辑思维能力。

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

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

在寻找计算问题的解决方案时，我们经常使用回溯算法。在解决数独时，它检查已填充的格子的数字是否有效。

如果数字无效，它会检查从1到9的其他数字。如果找不到有效数字，它将回溯到前一个选项。

当我们遇到死胡同并返回到先前的选择时，我们已经做出了一个选择并将更改我们的选择，从而得到一个不同的可能解。

让我们采用实现数独求解器和回溯算法的方法。

首先，我们需要通过形成谜题来设置数独板。

def setBoardFunc(puz):global gridprint('\n---------------数独求解器---------------\n')print('数独问题如下：')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()的函数来形成数独谜题。在循环过程中，它设置一个9x9的谜题，并用0初始化空单元格。

完成函数操作后，它打印出给定的输入。然后我们需要打印出数独格局；这一步打印出带有给定输入的9x9格局。

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

接下来，我们将检查当前值是否可以放置在当前格子中。

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

这一步检查给定的数字是否适用于特定的格子。该数字不能是同一行、同一列或同一块中的任何其他格子。

如果数字满足该要求并返回true，则可以移动到下一个值；否则，该数字被拒绝。然后我们必须遍历所有块来适应回溯算法。

def solveFunc():global gridfor 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] = numsolveFunc()grid[row][column] = 0returnprint('\n数独问题的解决方案：')printGridFunc()

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

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

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

当算法使用有效数字填充空格直到死胡同时，它会回溯过程并重新迭代整个过程。最后，让我们传递数独格局并调用函数来解决给定的数独谜题。

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

完整的源代码：

def setBoardFunc(puz):global gridprint('\n---------------数独求解器---------------\n')print('数独问题如下：')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 gridfor row in grid:print(row)def checkValidFunc(row,column,num):global gridfor i in range(0,9):if grid[row][i] == num:return Falsefor i in range(0,9):if grid[i][column] == num:return Falsesquare_row = (row//3)*3square_col = (column//3)*3for i in range(0,3):for j in range(0,3):if grid[square_row+i][square_col+j] == num:return Falsereturn Truedef solveFunc():global gridfor 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] = numsolveFunc()grid[row][column] = 0returnprint('\n数独问题的解决方案：')printGridFunc()puz = "004300209005009001070060043006002087190007400050083000600000105003508690042910300"
grid = []
setBoardFunc(puz)
solveFunc()