n皇后
时间: 2023-09-15 10:22:24 浏览: 47
n 皇后问题是一个经典的回溯算法问题,它的目标是在 n × n 的棋盘上放置 n 个皇后,使得每个皇后都不会在同一行、同一列或同一对角线上。如果存在解决方案,则输出其中一组解。
解决这个问题的常见方法是使用回溯算法。具体来说,可以从第一行开始,尝试在每个位置放置皇后,并检查是否满足条件。如果当前位置可以放置皇后,则继续递归到下一行;否则回溯到上一行,并尝试在上一行的下一个位置放置皇后。如果已经放置了 n 个皇后,则找到了一组解决方案。
以下是 Python 代码示例:
```python
def solve_n_queens(n):
def is_valid(board, row, col):
# 检查行和列
for i in range(n):
if board[i][col] == 1:
return False
if board[row][i] == 1:
return False
# 检查对角线
for i in range(n):
for j in range(n):
if i + j == row + col or i - j == row - col:
if board[i][j] == 1:
return False
return True
def backtrack(board, row):
if row == n:
res.append(["".join(["Q" if i == 1 else "." for i in row]) for row in board])
return
for col in range(n):
if is_valid(board, row, col):
board[row][col] = 1
backtrack(board, row + 1)
board[row][col] = 0
res = []
board = [[0] * n for _ in range(n)]
backtrack(board, 0)
return res
```
该算法的时间复杂度为 O(n!),空间复杂度为 O(n^2)。