编写一个函数,求解皇后问题:在 $n \times n$ 的方格棋盘上,放置 $n$ 个皇后,要求每个皇后不同行、不同列、不同左右对角线。
时间: 2023-06-11 11:10:02 浏览: 59
以下是 Python 代码实现:
```python
# 检查当前位置是否合法
def isValid(board, row, col, n):
# 检查列是否合法
for i in range(n):
if board[i][col] == 'Q':
return False
# 检查左上方是否有皇后冲突
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i, j = i - 1, j - 1
# 检查右上方是否有皇后冲突
i, j = row - 1, col + 1
while i >= 0 and j < n:
if board[i][j] == 'Q':
return False
i, j = 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 isValid(board, row, col, n):
board[row][col] = 'Q'
backtrack(board, row + 1, n, res)
board[row][col] = '.'
# 主函数
def solveNQueens(n):
board = [['.' for _ in range(n)] for _ in range(n)]
res = []
backtrack(board, 0, n, res)
return res
```
其中,isValid 函数用于检查当前位置是否合法,backtrack 函数用于递归求解,solveNQueens 函数是主函数,返回所有合法的解。
时间复杂度为 $O(n^n)$,空间复杂度为 $O(n^2)$。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)