代码实现递归八皇后问题
时间: 2024-09-15 12:07:13 浏览: 22
递归八皇后问题是经典的计算机科学问题,它的目标是在一个8x8的棋盘上放置8个皇后,使得任意两个皇后都不在同一行、同一列,以及斜线上。下面是一个简单的Python代码示例,使用了回溯算法来解决这个问题:
```python
def is_safe(board, row, col):
# 检查列是否已经有皇后
for i in range(row):
if board[i] == col:
return False
# 检查左上角到右下角是否有皇后
start = max(0, col - row)
end = min(len(board) - 1, col + row)
for i in range(start, end + 1):
if board[i] == col or abs(board[i] - col) == i - row:
return False
return True
def solve_n_queens(board, n=8, col=-1):
# 如果已经放完所有皇后,返回True
if col >= n:
return True
for queen_col in range(n):
# 检查当前位置是否安全
if is_safe(board, len(board), queen_col):
# 放置皇后
board.append(queen_col)
# 继续尝试下一个位置
if solve_n_queens(board, n, queen_col + 1):
return True
# 回溯,移除当前皇后的位置
board.pop()
return False
# 初始化一个空列表作为棋盘
board = [-1] * 8
if solve_n_queens(board):
print("Solution exists:")
print(board)
else:
print("No solution found.")
```