Python 8 puzzle BFS infinite loop -

i trying solve 8 puzzle problem using bfs search, however, code seems stuck in infinite loop moves 0 tile , forth until memory of queue ends program in error.

import collections import queue  class node:  def __init__(self, puzzle, last=none):         self.puzzle = puzzle         self.last = last      @property     def seq(self): # keep track of sequence used goal         node, seq = self, []         while node:             seq.append(node)             node = node.last         yield reversed(seq)      @property     def state(self):         return str(self) # hashable can 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 0 tile 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 @ time)      def move(self, current, to):          changeboard = self.board[:] # create copy         changeboard[to], changeboard[current] = changeboard[current], changeboard[to] # switch tiles @ passed positions         return puzzle(changeboard) # return new puzzle object      def printpuzzle(self): # prints board in 8 puzzle style          copyboard = self.board[:]         in range(9):             if == 2 or == 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 testing             if currentnode.puzzle.issolved:                 return currentnode.seq              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 move node in goalseq:     counter = counter + 1     node.puzzle.printpuzzle() print("total number of moves: " + counter) 

i thought adding each node set() stop code getting caught in loop. not true?

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

this return looks <__main__.node object @ 0x02173a90>. address unique per node object, state of 2 nodes identical boards still considered distinct set.

instead, try:

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

now 2 nodes identical boards considered same.

also, change last line of script

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

now result:

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