用python实现八皇后问题求解,以序列格式存储结果输出,例如 [0,6,4,7,1,3,5,2] 指代在第 0-7 行依次在指定列落子,通过self.solves.append([0,6,4,7,1,3,5,2]) 添加求解结果,最后结果以解的list格式输出
时间: 2023-05-25 12:03:40 浏览: 87
经典计算机科学问题的Python实现algorithm-learn-master.zip
以下是一个实现八皇后问题求解的示例代码:
```python
class EightQueens:
def __init__(self):
self.solves = []
def solve(self):
self._solve(8, [])
return self.solves
def _solve(self, n, positions):
if len(positions) == n:
self.solves.append(positions[:])
return
for i in range(n):
if self._is_valid(i, positions):
positions.append(i)
self._solve(n, positions)
positions.pop()
def _is_valid(self, col, positions):
row = len(positions)
for r, c in enumerate(positions):
if col == c or row - r == col - c or row - r == c - col:
return False
return True
eq = EightQueens()
solves = eq.solve()
for s in solves:
print(s)
```
在该实现中,`solve` 函数会返回一个包含所有可能的解法的列表。每个解法都是一个数组,其中第 i 个元素表示在第 i 行的皇后放在的列号。
在 `_solve` 函数中,我们使用回溯的策略来递归求解,尝试对每一行放置皇后的列进行遍历。对于每个列,我们检查当前位置是否合法,即是否在同一列、同一斜线上都没有其它皇后。如果当前位置合法,则将其加入到当前解法中,递归地继续考虑下一行的皇后放置。如果当前解法已经包含了所有 8 个皇后,就将解法保存到结果列表中,并回溯到上一行的决策点。
阅读全文