8 головоломка с использованием метода поиска в глубину

Question

Вот мой код для головоломки 8 с использованием dfs. Может кто-нибудь подскажет, как удалить повторяющиеся элементы из qList и visitList? Мне нужен только один элемент, представляющий одно состояние в очереди и посещенном списке. Задача решает задачу "8 головоломок" с помощью перебора в dfs. При выполнении он переходит в бесконечный цикл, поскольку он снова и снова расширяет один и тот же узел.

from copy import deepcopy
initState=[0,1,2,3,4,5,6,7,8]
goalState=[1,4,2,3,5,0,6,7,8]
q=[]
qList=[]
visited=[]
visitedList=[]
class state:
    def __init__(self,state=[],prev=None,tree=None):
        self.state=state
        self.children=[]
        self.parent=prev
        self.tree=[]
        if tree==None:
            self.tree.append(state)
        if tree is not None:
            self.tree.extend(deepcopy(tree)

    def sameState(self,state):
        return bool(state==self.state)

    def retState(self):
        return list(self.state)

    def isPrevState(self):
        if self.parent in self.children:
            self.children.remove(self.parent)

    def moveUp(self):
        child=deepcopy(self.state)
        if child.index(0)-3>=0:
            i=child.index(0)
            temp=child[i]
            child[i]=child[i-3]
            child[i-3]=temp
            children=state(child,self.state,self.tree)
            if children.state not in qList and children.state not in visitedList:
                self.children.append(children)
        else:
            del child

    def moveRight(self):
        child=deepcopy(self.state)
        if child.index(0)%3<2:
            i=child.index(0)
            temp=child[i]
            child[i]=child[i+1]
            child[i+1]=temp
            children=state(child,self.state,self.tree)
            if children.state not in qList and children.state not in visitedList:
                self.children.append(children)
        else:
            del child

    def moveLeft(self):
        child=deepcopy(self.state)
        if child.index(0)%3>0:
            i=child.index(0)
            temp=child[i]
            child[i]=child[i-1]
            child[i-1]=temp
            children=state(child,self.state,self.tree)
            if children.state not in qList and children.state not in visitedList:
                self.children.append(children)
        else:
            del child

    def moveDown(self):
        child=deepcopy(self.state)
        if child.index(0)+3<=8:
            i=child.index(0)
            temp=child[i]
            child[i]=child[i+3]
            child[i+3]=temp
            children=state(child,self.state,self.tree)
            if children.state not in qList and children.state not in visitedList:
                self.children.append(children)
        else:
            del child

    def expandNode(self):
        self.moveLeft()
        self.moveUp()
        self.moveRight()
        self.moveDown()
        self.isPrevState()
el=state(initState)
q.append(el)
while len(q)>0:
    if list(q[len(q)-1].retState())==goalState:
        print("goal state found")
        break
    else:
        if q[len(q)-1] not in visited:
            q[len(q)-1].expandNode()
            visited.append(deepcopy(q[len(q)-1]))
            visitedList.append((q[len(q)-1].retState()))
            List=q[len(q)-1].children
            for i in range(len(List)):
                q.append(List[i])
                if List[i].retState not in qList and List[i] not in visitedList :
                    qList.append(List[i].retState())
            nq=list(dict.fromkeys(q))
            q.clear()
            q=nq 
            q.pop()
        else:
            del q[len(q)-1]