深度优先搜索解决难题

Question

假设代码puzzle.extensions(self)已经被定义，它会return列出拼图的可用解法但不确定是否解法。另外定义了puzzle.is_solved(self)，判断这个解是否求解。这是我需要写的代码，我也做了一些不正确的工作。

def depth_first_solve(puzzle):
    """
    Return a path from PuzzleNode(puzzle) to a PuzzleNode containing
    a solution, with each child containing an extension of the puzzle
    in its parent.  Return None if this is not possible.

    @type puzzle: Puzzle
    @rtype: PuzzleNode
    """
    stack = [puzzle]
    while stack:
        k = stack.pop()
        for puzzle1 in puzzle.extensions():
            if not puzzle1.is_solved():
                stack+=[k,puzzle1]
            if puzzle1.is_solved():
                p = stack.pop()
                end_node = PuzzleNode(k,None, p)
                k = stack.pop()
                last_node = PuzzleNode(p,end_node,k)
                while stack:
                    k = p
                    p = stack.pop()
                    cur_node = PuzzleNode(k, last_node, p)
                    last_node = cur_node
                return cur_node

def __init__(self, puzzle=None, children=None, parent=None):
    """
    Create a new puzzle node self with configuration puzzle.

    @type self: PuzzleNode
    @type puzzle: Puzzle | None
    @type children: list[PuzzleNode]
    @type parent: PuzzleNode | None
    @rtype: None
    """
    self.puzzle, self.parent = puzzle, parent
    if children is None:
        self.children = []
    else:
        self.children = children[:]

好吧，我运行这些模块在拼图，它总是在等待结果，但什么也没有发生，所以谁能告诉我哪里错了？

Answer 1

我认为这段代码存在很多问题。首先，您总是在 puzzle.extensions() 上迭代，而不是在刚刚从堆栈中弹出的 k 节点的 extensions 上迭代。我怀疑这就是您获得无限循环的原因，因为相同的节点不断被推入堆栈（并被其余代码忽略）。

我不太确定为什么要使用 stack+=[k,puzzle1] 将 k 添加回堆栈。我很确定你只是想要 stack.append(puzzle1) 那里，除非你正在尝试一些我不理解的非常微妙的东西。

深度优先搜索解决难题

Depth first search to Solve puzzle

python

linked-list

depth-first-search

python-3.x