n皇后python回溯法
时间: 2023-09-15 13:23:20 浏览: 80
下面是一个基于回溯法的 n 皇后 Python 实现:
```python
def solveNQueens(n):
def is_valid(board, row, col):
for i in range(row):
if board[i] == col or abs(board[i] - col) == row - i:
return False
return True
def backtrack(board, row):
if row == n:
res.append(list(board))
return
for col in range(n):
if is_valid(board, row, col):
board[row] = col
backtrack(board, row + 1)
board[row] = -1
res = []
board = [-1] * n
backtrack(board, 0)
return res
```
这里采用一个一维数组 `board` 来表示棋盘,`board[i]` 表示第 i 行皇后所在的列数,初始值为 -1。在每一行中,我们枚举该行所有列,如果可以放置皇后,则将其放置在该位置,并递归处理下一行。如果发现该位置无法放置皇后,则回溯到上一行重新处理。
`is_valid()` 函数用于判断当前位置是否可以放置皇后。若在同一列或同一对角线上已经有皇后,则返回 False。如果没有冲突,则返回 True。
最终返回的是所有可行的皇后摆法,每一种摆法都表示为一个长度为 n 的列表,列表的第 i 个元素表示第 i 行皇后所在的列数。
阅读全文