def conflict(state, nextX): nextY = len(state) for i in range(nextY): if abs(state[i]-nextX) in (0, nextY-i): return True return False
时间: 2024-04-28 07:20:11 浏览: 16
这是一个关于 N 皇后问题的冲突检测函数,用于判断下一个皇后放置在哪个位置时是否与已有的皇后冲突。其中 state 是一个列表,存储每一行皇后的列坐标,nextX 是下一个皇后要放置的列坐标。函数会计算出 nextX 和已有皇后的坐标之间的行距和列距是否相等,如果相等则表示存在冲突,返回 True,否则返回 False。
相关问题
利用python分别采用递归和迭代两种算法解决八皇后问题,
八皇后问题是一个经典的回溯算法问题,其目标是在一个8×8的棋盘上放置8个皇后,使得任意两个皇后都不能处于同一行、同一列或同一斜线上。
递归实现八皇后问题:
```python
def conflict(state, nextX):
nextY = len(state)
for i in range(nextY):
if abs(state[i]-nextX) in (0, nextY-i):
return True
return False
def queens(num=8, state=()):
for pos in range(num):
if not conflict(state, pos):
if len(state) == num-1:
yield (pos,)
else:
for result in queens(num, state+(pos,)):
yield (pos,)+result
for solution in queens():
print(solution)
```
迭代实现八皇后问题:
```python
def queens(num=8):
solutions = [(pos,) for pos in range(num)]
for i in range(num-1):
solutions = [solution+(pos,)
for solution in solutions
for pos in range(num)
if not conflict(solution, pos)]
return solutions
def conflict(state, nextX):
nextY = len(state)
for i in range(nextY):
if abs(state[i]-nextX) in (0, nextY-i):
return True
return False
for solution in queens():
print(solution)
```
以上两种算法都可以求出八皇后问题的解,但递归算法更加简洁易懂,而迭代算法则更加直观易懂。
八皇后问题python源代码
可以参考以下代码:
```python
def conflict(state, nextx):
nexty = len(state)
for i in range(nexty):
if abs(state[i] - nextx) in (0, nexty-i):
return True
return False
def queens(num=8, state=()):
for pos in range(num):
if not conflict(state, pos):
if len(state) == num-1:
yield (pos,)
else:
for result in queens(num, state+(pos,)):
yield (pos,) + result
def prettyprint(solution):
def line(pos, length=len(solution)):
return '. ' * (pos) + 'X ' + '. '*(length-pos-1)
for pos in solution:
print(line(pos))
for solution in queens(8):
print(solution)
prettyprint(solution)
```
注意,八皇后问题有多种解法,上面的代码只展示其中一种实现方式。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)