Глубина первого поиска для решения головоломки

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(), а не на extensions узла k, который вы только что выскочили со стека. Я подозреваю, что именно поэтому вы получаете бесконечный цикл, так как одни и те же узлы постоянно переходят в стек и игнорируются остальной частью кода.

Я не совсем уверен, почему вы добавляете k обратно в стек, хотя с stack+=[k,puzzle1]. Я почти уверен, что вы просто хотите stack.append(puzzle1) там, если вы не пытаетесь что-то действительно тонкое, что я не понимаю.