Python 8 puzzle BFS бесконечный цикл

Question

Я пытаюсь решить проблему с 8 головоломками, используя BFS-поиск, однако мой код, кажется, застревает в бесконечном цикле, где он только перемещает нулевую плиту туда и обратно, пока память очереди завершает программу с ошибкой.

import collections 
import queue 

class Node: 

def __init__(self, puzzle, last=None): 
     self.puzzle = puzzle 
     self.last = last 

    @property 
    def seq(self): # to keep track of the sequence used to get to the goal 
     node, seq = self, [] 
     while node: 
      seq.append(node) 
      node = node.last 
     yield from reversed(seq) 

    @property 
    def state(self): 
     return str(self) # hashable so it can be compared in sets 

    @property 
    def isSolved(self): 
     return self.puzzle.isSolved 

    @property 
    def getMoves(self): 
     return self.puzzle.getMoves 

class Puzzle: 

    def __init__(self, startBoard): 
     self.board = startBoard 

    @property 
    def getMoves(self): 

     possibleNewBoards = [] 

     zeroPos = self.board.index(0) # find the zero tile to determine possible moves 

     if zeroPos == 0: 
      possibleNewBoards.append(self.move(0,1)) 
      possibleNewBoards.append(self.move(0,3)) 
     elif zeroPos == 1: 
      possibleNewBoards.append(self.move(1,0)) 
      possibleNewBoards.append(self.move(1,2)) 
      possibleNewBoards.append(self.move(1,4)) 
     elif zeroPos == 2: 
      possibleNewBoards.append(self.move(2,1)) 
      possibleNewBoards.append(self.move(2,5)) 
     elif zeroPos == 3: 
      possibleNewBoards.append(self.move(3,0)) 
      possibleNewBoards.append(self.move(3,4)) 
      possibleNewBoards.append(self.move(3,6)) 
     elif zeroPos == 4: 
      possibleNewBoards.append(self.move(4,1)) 
      possibleNewBoards.append(self.move(4,3)) 
      possibleNewBoards.append(self.move(4,5)) 
      possibleNewBoards.append(self.move(4,7)) 
     elif zeroPos == 5: 
      possibleNewBoards.append(self.move(5,2)) 
      possibleNewBoards.append(self.move(5,4)) 
      possibleNewBoards.append(self.move(5,8)) 
     elif zeroPos == 6: 
      possibleNewBoards.append(self.move(6,3)) 
      possibleNewBoards.append(self.move(6,7)) 
     elif zeroPos == 7: 
      possibleNewBoards.append(self.move(7,4)) 
      possibleNewBoards.append(self.move(7,6)) 
      possibleNewBoards.append(self.move(7,8)) 
     else: 
      possibleNewBoards.append(self.move(8,5)) 
      possibleNewBoards.append(self.move(8,7)) 

     return possibleNewBoards # returns Puzzle objects (maximum of 4 at a time) 

    def move(self, current, to): 

     changeBoard = self.board[:] # create a copy 
     changeBoard[to], changeBoard[current] = changeBoard[current], changeBoard[to] # switch the tiles at the passed positions 
     return Puzzle(changeBoard) # return a new Puzzle object 

    def printPuzzle(self): # prints board in 8 puzzle style 

     copyBoard = self.board[:] 
     for i in range(9): 
      if i == 2 or i == 5: 
       print((str)(copyBoard[i])) 
      else: 
       print((str)(copyBoard[i])+" ", end="") 
     print('\n') 

    @property 
    def isSolved(self): 
     return self.board == [0,1,2,3,4,5,6,7,8] # goal board 

class Solver: 

    def __init__(self, Puzzle): 
     self.puzzle = Puzzle 

    def solveBFS(self): 
     startNode = Node(self.puzzle) 
     myQueue = collections.deque([startNode]) 
     visited = set() 
     visited.add(myQueue[0].state) 
     while myQueue: 
      currentNode = myQueue.pop() 
      # currentNode.puzzle.printPuzzle() # used for testing 
      if currentNode.puzzle.isSolved: 
       return currentNode.seq 

      for board in currentNode.getMoves: 
       nextNode = Node(board, currentNode) 

       if nextNode.state not in visited: 
        myQueue.appendleft(nextNode) 
        visited.add(nextNode.state) 

startingBoard = [7,2,4,5,0,6,8,3,1] 

myPuzzle = Puzzle(startingBoard) 
mySolver = Solver(myPuzzle) 
goalSeq = mySolver.solveBFS() 

counter = -1 # starting state doesn't count as a move 
for node in goalSeq: 
    counter = counter + 1 
    node.puzzle.printPuzzle() 
print("Total number of moves: " + counter) 

Я думал, что добавление каждого узла к set() бы остановить код от попасться в петлю. Разве это не так?

Answer 1

@property 
def state(self): 
    return str(self) # hashable so it can be compared in sets 

Это вернет что-то похожее на <__main__.Node object at 0x02173A90>. Адрес уникален для каждого объекта Node, поэтому state из двух узлов с одинаковыми платами по-прежнему будет считаться отличным от набора.

Вместо этого попробуйте:

@property 
def state(self): 
    return str(self.puzzle.board) 

Теперь два узла с одинаковыми платами будут считаться одинаковыми.

Кроме того, измените последнюю строку вашего сценария

print("Total number of moves: " + str(counter)) 

Теперь вы получите результат:

7 2 4 
5 0 6 
8 3 1 

7 2 4 
0 5 6 
8 3 1 

(snip) 

1 0 2 
3 4 5 
6 7 8 

0 1 2 
3 4 5 
6 7 8 

Total number of moves: 26