Tiefe erste Suche zu lösen Puzzle

Question

Angenommen, der Code puzzle.extensions(self) wurde bereits definiert, und es wird eine Liste der verfügbaren Lösungen des Puzzles zurückgeben, aber ohne die Bestimmung, ob es gelöst ist. Auch puzzle.is_solved(self) wurde definiert und es wird festgestellt, ob diese Lösung gelöst ist. Hier ist der Code, den ich schreiben muss, ich mache auch einige falsche Arbeiten.

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

Nun betreibe ich diese Module in Puzzle, und es wartet immer auf Ergebnisse, und nichts geschieht, so könnte mir jemand sagen, dass, wo ich es falsch?

Answer 1

Ich denke, es gibt eine sehr große Anzahl von Problemen mit diesem Code. Zu Beginn iterieren Sie immer auf puzzle.extensions() und nicht auf dem extensions des k-Knotens, den Sie gerade vom Stapel genommen haben. Ich vermute, das ist der Grund, warum Sie eine Endlosschleife erhalten, da dieselben Knoten immer wieder auf den Stapel geschoben werden (und vom Rest des Codes ignoriert werden).

Ich bin nicht wirklich sicher, warum Sie k mit stack+=[k,puzzle1] zurück zum Stapel hinzufügen. Ich bin mir ziemlich sicher, dass du nur stack.append(puzzle1) da haben willst, außer du versuchst etwas wirklich Subtiles, das ich nicht verstehe.