深度第一次搜索解決拼圖

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，您剛剛彈出堆棧。我懷疑這就是爲什麼你會得到一個無限循環，因爲相同的節點不斷被反覆壓入堆棧（並被其餘代碼忽略）。

我不確定你爲什麼要將k加回堆棧，但使用stack+=[k,puzzle1]。我很確定你只想stack.append(puzzle1)那裏，除非你嘗試了一些我不明白的東西。