深度优先搜索法求解puzz

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[:]

好吧，我在puzzle中运行这些模块，它总是在等待结果，什么也没有发生，所以有人能告诉我我哪里弄错了吗？在

Answer 1

我认为这个代码有很多问题。首先，您总是在puzzle.extensions()上迭代，而不是在刚刚从堆栈中弹出的k节点的extensions上迭代。我怀疑这就是为什么你会得到一个无限循环，因为相同的节点不断地被推到堆栈上（并且被其他代码忽略）。在

我不太清楚为什么要用stack+=[k,puzzle1]将k添加回堆栈。我真的不想让你明白。在