这是一个创建于 2420 天前的主题，其中的信息可能已经有所发展或是发生改变。
def queens(num=8, state=()): # 生成器函数 for pos in range(num): if not conflict(state, pos): # 到达最后一行时返回(pos,) if len(state) == num - 1: yield (pos,) # 只有一个元素的元组 else: for result in queens(num, state + (pos,)): # result 在返回的生成器中迭代 yield (pos,) + result
这个是如何实现回溯算法的，比如说到了（ 0.2.4.1.3 ）之后发现没有位置可以放，怎么退回到上一步变成（ 0.2.4.1.7 ）
 |
1
aheadlead 2018-04-08 19:24:48 +08:00
|
 |
2
yemenchun1 2018-04-08 20:17:02 +08:00 via iPhone
else 后面递归调用 queens 函数了
|
 |
3
fromxt 2018-04-09 10:36:58 +08:00
这好像是《 python 基础教程》的一个例子吧。
回溯算法我是这么理解的。例如只有 4 个皇后 （ num=4 ） 记住是从 pos=0 开始，第 1 个皇后的位置就有 0，1, 2, 3 这四个可能. 从 pos =0 开始，通过 conflict(state, pos)函数，判断满足条件的第 2 个皇后的位置，然后第 3 个，第 4 个。这就找到了满足条件的位置。这时候就是会退到 pos =1 的位置，然后按照前面的流程走。 if len(state) == num - 1 这个就是前三个皇后位置已经确定了 找最后一个皇后位置。 反复读读那本书第 9 章第 8 节，^_^应该好理解了。 |
Select Language