完成数独的算法 python_数独(Sudoku)问题的Python实现
时间: 2024-03-03 12:49:25 浏览: 13
好的,以下是一个简单的 Python 实现数独的算法:
```python
def print_board(board):
"""
打印数独棋盘
"""
for i in range(9):
for j in range(9):
print(board[i][j], end=" ")
print()
def find_empty(board):
"""
查找数独棋盘中的空格
"""
for i in range(9):
for j in range(9):
if board[i][j] == 0:
return (i, j)
return None
def is_valid(board, num, pos):
"""
检查数独棋盘中的数字是否合法
"""
# 检查行
for i in range(9):
if board[pos[0]][i] == num and pos[1] != i:
return False
# 检查列
for i in range(9):
if board[i][pos[1]] == num and pos[0] != i:
return False
# 检查 3x3 方格
box_x = pos[1] // 3
box_y = pos[0] // 3
for i in range(box_y * 3, box_y * 3 + 3):
for j in range(box_x * 3, box_x * 3 + 3):
if board[i][j] == num and (i, j) != pos:
return False
return True
def solve(board):
"""
解决数独棋盘
"""
# 查找空格
find = find_empty(board)
if not find:
return True
else:
row, col = find
# 尝试填入数字
for i in range(1, 10):
if is_valid(board, i, (row, col)):
board[row][col] = i
if solve(board):
return True
board[row][col] = 0
return False
# 测试
board = [
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0]
]
print("原始棋盘:")
print_board(board)
solve(board)
print("解决的棋盘:")
print_board(board)
```
该算法的思路是通过递归查找数独棋盘中的空格,并尝试填入数字,直到棋盘被解决或无法填入数字。在填入数字之前,需要检查该数字是否在行、列和 3x3 方格中已经出现过,以确保填入数字的合法性。