深さの最初の探索でのパズルの解決

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

私はこのコードには非常に多くの問題があると思います。まず、ノードのextensionsではなく、puzzle.extensions()のノードを繰り返し繰り返しています。私は、同じノードが何度も繰り返しスタックにプッシュされ続けるため（そして、コードの残りの部分では無視されるため）、無限ループを起こしているのではないかと疑います。

stack+=[k,puzzle1]と一緒にkをスタックに追加する理由がわかりません。私はあなたが理解していない本当に微妙なものを試していない限り、そこにstack.append(puzzle1)がほしいと確信しています。