深度优先搜索以解决谜题

Question

假设代码puzzle.extensions(self)已经定义，它将返回一个列表，列出谜题的可用解决方案，但不确定是否已解决。此外，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)，除非你在尝试一些我不理解的非常微妙的事情。