Python递归实现数独问题

2023-04-15 00:00:00 python 递归数独

数独问题是一种填数游戏，需要在99的网格中填入数字，使得每一行、每一列和每一个33的九宫格中的数字都是1-9，且不能重复。本文将介绍如何使用Python递归来解决数独问题。

首先，我们需要定义一个函数来检查一个数字是否可以放在指定的行、列或九宫格中。这个函数可以使用循环来实现。

def is_valid(board, row, col, num):
# check row
for i in range(9):
if board[row][i] == num:
return False
# check column
for i in range(9):
if board[i][col] == num:
return False
# check square
r = row // 3 * 3
c = col // 3 * 3
for i in range(r, r+3):
for j in range(c, c+3):
if board[i][j] == num:
return False
return True

这个函数会接收一个数独板的二维列表、行、列和数字作为参数，然后分别检查这个数字在行、列和九宫格中是否已经存在。如果不存在，就返回True，否则返回False。

下一步，我们需要定义一个递归函数来填充数独板。对于每个空格，我们都需要尝试填入数字1-9，然后检查是否有效。如果有效，就递归到下一个空格，如果无效，就试下一个数字。如果所有数字都尝试过了还无法完成数独板的填充，那么就回溯到上一个空格。

def solve(board, row=0, col=0):
if row == 9:
return True
if col == 9:
return solve(board, row+1, 0)
if board[row][col] != 0:
return solve(board, row, col+1)
for i in range(1, 10):
if is_valid(board, row, col, i):
board[row][col] = i
if solve(board, row, col+1):
return True
board[row][col] = 0
return False

这个函数会接收一个数独板的二维列表和当前要填充的行和列作为参数。如果某一行已经填充完了，就返回True；如果当前列已经是第9列，就递归到下一行；如果当前格子已经填好了，就递归到下一个格子。如果当前格子是空的，就从1-9中尝试一个数字，然后检查是否有效。如果有效，就填入这个数字，然后递归到下一个格子。如果无法有效填入，就回溯到上一个格子，重复以上过程。

最后，我们可以使用这个函数来解决给定的数独问题，例如：

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

solve(board)

print(board)

在这个例子中，我们使用了一个二维数组来表示数独问题。其中，数字0表示空格，需要我们填入合适的数字。使用solve函数来解决这个问题，最后打印出填好数字的数独板即可。

完整代码如下：

solve(board)

print(board)

相关文章