python八皇后问题
时间: 2023-06-30 19:03:07 浏览: 35
八皇后问题是一个经典的回溯算法问题,要求将8个皇后放在8×8的棋盘上,使得任意两个皇后都不能在同一行、列、对角线上。以下是Python实现代码:
```python
def is_valid(board, row, col):
"""
判断当前位置是否可以放置皇后
"""
for i in range(row):
if board[i] == col or abs(board[i] - col) == abs(i - row):
return False
return True
def backtrack(board, row, res):
"""
回溯函数
"""
n = len(board)
if row == n:
res.append(board[:])
return
for col in range(n):
if is_valid(board, row, col):
board[row] = col
backtrack(board, row + 1, res)
board[row] = -1
def solve_n_queens(n):
"""
求解n皇后问题
"""
board = [-1] * n
res = []
backtrack(board, 0, res)
return res
```
其中,`is_valid`函数用于判断当前位置是否可以放置皇后,`backtrack`函数用于进行回溯搜索,`solve_n_queens`函数是对外的求解接口,返回所有解法。