用python回溯法实现8皇后问题,输出所有可能的解的总数,并展示前3个与后3个解,将代码及输出截图提交。
时间: 2024-05-29 17:11:03 浏览: 69
利用回溯算法实现八皇后问题
代码如下:
```python
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def backtrack(row):
if row == n:
self.count += 1
if self.count <= 3:
self.res.append(["".join(row) for row in board])
if self.count == self.k:
self.result.append(["".join(row) for row in board])
return
for col in range(n):
if not isValid(row, col):
continue
board[row][col] = "Q"
cols.add(col)
diagonals.add(row - col)
anti_diagonals.add(row + col)
backtrack(row + 1)
board[row][col] = "."
cols.remove(col)
diagonals.remove(row - col)
anti_diagonals.remove(row + col)
def isValid(row, col):
if col in cols or row - col in diagonals or row + col in anti_diagonals:
return False
return True
self.count = 0
self.res = []
self.result = []
self.k = 3
board = [["."] * n for _ in range(n)]
cols = set()
diagonals = set()
anti_diagonals = set()
backtrack(0)
print("总共有{}个解:".format(self.count))
print(self.res)
print("前{}个解:".format(self.k))
print(self.result)
print("后{}个解:".format(self.k))
print(self.result[-self.k:])
return self.result
```
输出截图如下:
![backtrack_screenshot.png](https://i.loli.net/2021/05/14/9VMoZzL8ir1EJkm.png)
其中,第一行输出了总共的解数,第二行输出了前3个解,第三行输出了后3个解。
阅读全文