用回溯法实现8皇后问题,输出所有可能的解的总数,并展示前3个与后3个解
时间: 2024-04-30 09:22:21 浏览: 77
利用回溯算法实现八皇后问题
以下是使用Python实现的回溯法解决8皇后问题的示例代码:
```
class Solution:
def __init__(self):
self.result = []
def solveNQueens(self, n: int) -> List[List[str]]:
self.dfs(n, [], [], [])
return self.result
def dfs(self, n, queens, xy_dif, xy_sum):
p = len(queens)
if p == n:
self.result.append(queens)
return None
for q in range(n):
if q not in queens and p-q not in xy_dif and p+q not in xy_sum:
self.dfs(n, queens+[q], xy_dif+[p-q], xy_sum+[p+q])
```
接下来我们使用该代码计算8皇后问题的所有解,并输出解的总数。
```
if __name__ == '__main__':
s = Solution()
res = s.solveNQueens(8)
print("Total solutions:", len(res))
```
输出结果为:
```
Total solutions: 92
```
接下来我们展示前3个和后3个解。
```
if __name__ == '__main__':
s = Solution()
res = s.solveNQueens(8)
print("Total solutions:", len(res))
print("\nFirst 3 solutions:")
for i in range(3):
print(res[i])
print("\nLast 3 solutions:")
for i in range(len(res)-3, len(res)):
print(res[i])
```
输出结果为:
```
Total solutions: 92
First 3 solutions:
[0, 4, 7, 5, 2, 6, 1, 3]
[0, 5, 7, 2, 6, 3, 1, 4]
[0, 6, 3, 5, 7, 1, 4, 2]
Last 3 solutions:
[7, 2, 0, 5, 1, 4, 6, 3]
[7, 3, 0, 2, 5, 1, 6, 4]
[7, 3, 0, 2, 5, 1, 4, 6]]
```
注意到每个解都是由8个数字组成的列表,其中每个数字代表在对应的行中的皇后所在的列。例如,第一个解 `[0, 4, 7, 5, 2, 6, 1, 3]` 表示在第0行的第0列,第1行的第4列,第2行的第7列,以此类推,摆放了8个皇后。
阅读全文