python 八皇后程序
时间: 2024-01-05 08:47:52 浏览: 15
由于这是一道经典的算法问题,因此有很多种不同的实现方式。下面是一种基于回溯算法的 Python 实现:
```python
def EightQueen(row=0, queens=[]):
if row == 8:
print(queens)
return
for col in range(8):
if isSafe(row, col, queens):
queens.append((row, col))
EightQueen(row + 1, queens)
queens.pop()
def isSafe(row, col, queens):
for r, c in queens:
if col == c or row - col == r - c or row + col == r + c:
return False
return True
EightQueen()
```
该程序的核心是 `EightQueen` 函数,它使用递归来搜索所有可能的解决方案。在每一行中,我们尝试将皇后放置在每一列上。如果当前位置是安全的,则将其添加到皇后列表中,并继续递归到下一行。如果递归到第 8 行,意味着我们已经找到了一个有效的解决方案,并打印出来。在回溯时,我们将最后添加的皇后弹出列表,以便尝试下一个位置。
`isSafe` 函数用于检查当前位置是否与之前放置的皇后相冲突。如果在同一列、同一行或同一对角线上,则两个皇后会相互攻击,因此当前位置不是安全的。否则,它是安全的并可以放置一个皇后。
这个程序可以打印出所有的八皇后解决方案。但是,由于八皇后问题的对称性,会有很多重复的解决方案。因此,如果只需要计数或找到一个解决方案,则可以对程序进行一些修改。