给我一个python的代码实现
时间: 2024-10-22 22:23:53 浏览: 12
当然可以。这里是一个简单的Python代码实现,用于解决八皇后问题:
```python
def is_safe(board, row, col):
# 检查列是否有皇后
for i in range(row):
if board[i] == col:
return False
# 检查左上方对角线是否有皇后
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i] == j:
return False
i, j = i - 1, j - 1
# 检查右上方对角线是否有皇后
i, j = row - 1, col + 1
while i >= 0 and j < 8:
if board[i] == j:
return False
i, j = i - 1, j + 1
return True
def solve_n_queens(board, n, col):
# 基本情况:当放置完所有皇后,返回True
if col >= n:
return True
# 对于每行,尝试将皇后放在这个位置
for r in range(n):
if is_safe(board, r, col):
# 将皇后放在这行这列
board[r] = col
# 递归检查下一行
if solve_n_queens(board, n, col + 1):
return True
# 回溯:如果在某一步无法放置,撤消并尝试下一个位置
board[r] = -1
# 如果没有找到合法的放置位置,返回False
return False
# 初始化一个空棋盘
board = [-1] * 8
# 解决八皇后问题
if solve_n_queens(board, 8, 0):
print("皇后可以在以下行放置:", [i for i, x in enumerate(board) if x != -1])
else:
print("No Answer")
```
这段代码首先定义了一个 `is_safe` 函数,用于检查当前位置是否安全。然后在 `solve_n_queens` 函数中,通过递归来尝试每一行每一列的可能性,直到找到所有皇后的合法位置。如果没有找到,会回溯到上一步。最后,检查函数是否成功解决了问题,并打印出结果。如果无解则输出"No Answer"。
阅读全文