用python实现八皇后问题求解,编写def run函数,以序列格式存储结果输出,例如 [0,6,4,7,1,3,5,2] 指代在第 0-7 行依次在指定列落子,通过self.solves.append([0,6,4,7,1,3,5,2]) 添加求解结果,最后结果以解的list格式输出,不用给出结果
时间: 2023-05-24 08:07:22 浏览: 68
python实现的八皇后问题
以下是八皇后问题的 Python 代码实现:
```python
class EightQueens:
def __init__(self):
self.solves = []
def run(self):
def is_valid(board, row, col):
for i in range(row):
if board[i] == col or abs(board[i] - col) == abs(i - row):
return False
return True
def backtrack(board, row):
if row == len(board):
self.solves.append(board[:])
return
for col in range(len(board)):
if is_valid(board, row, col):
board[row] = col
backtrack(board, row+1)
board[row] = -1
board = [-1] * 8
backtrack(board, 0)
return self.solves
```
函数 `run()` 实现了八皇后问题的求解,返回所有的解集。其中,`is_valid()` 函数用于判断在当前的放置方案下,第 `row` 行的皇后是否可以被安全放置在第 `col` 列。`backtrack()` 函数用于回溯搜索所有的解集,`board` 数组表示当前的放置方案,`row` 表示当前正在放置的皇后行数。
在 `backtrack()` 函数中,当 `row` 的值等于 `board` 的长度时,说明所有行的皇后均已正确放置,将当前方案加入 `self.solves` 数组中即可。
运行 `EightQueens().run()` 函数将会得到所有的八皇后问题的解集。
阅读全文