n皇后问题回溯法用python
时间: 2023-08-04 16:36:36 浏览: 50
好的,以下是使用回溯法解决 n 皇后问题的 Python 代码:
```python
def is_valid(board, row, col, n):
# 检查同一列上是否有皇后
for i in range(row):
if board[i][col] == 'Q':
return False
# 检查左上方是否有皇后
i = row - 1
j = col - 1
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
# 检查右上方是否有皇后
i = row - 1
j = col + 1
while i >= 0 and j < n:
if board[i][j] == 'Q':
return False
i -= 1
j += 1
return True
def backtrack(board, row, n, res):
if row == n:
res.append([''.join(row) for row in board])
return
for col in range(n):
if is_valid(board, row, col, n):
board[row][col] = 'Q'
backtrack(board, row + 1, n, res)
board[row][col] = '.'
def solve_n_queens(n):
board = [['.' for _ in range(n)] for _ in range(n)]
res = []
backtrack(board, 0, n, res)
return res
```
该函数 `solve_n_queens(n)` 的参数 `n` 代表 n 皇后问题的规模,返回一个列表,其中每个元素表示一个可行的解法,每个解法是一个 n × n 的棋盘,其中 Q 表示皇后的位置。