Codigo solucion 8 puzzle (python)

import random
import Queue as queue

class Tablero():

    def __init__(self,tsolv):
        self.tablero=tsolv
        self.tablerometa=[]
        cont=1
        for i in range(len(tsolv)):
            self.tablerometa.append([])
            for j in range(len(tsolv)):
                self.tablerometa[i].append(cont)
                cont=cont+1
        self.tablerometa[len(tsolv)-1][len(tsolv)-1]=0

    def Size(self):
        return len(self.tablero)

    def EsSolucion(self):
        tmp=[]
        inv=0
        for i in range(self.Size()):
            for j in range (self.Size()):
                if self.tablero[i][j]!=0:
                    tmp.append(self.tablero[i][j])

        for m in range(len(tmp)):
            for i in range (len(tmp)-m):
                if tmp[m]>tmp[i+m]:
                    inv=inv+1
                   
        if (inv%2)==0:
            return True
        else:
            return False
     
    def Copia(self):
        copia = self.tablero[:]
        for i in range(self.Size()):
            copia[i]=self.tablero[i][:]
        return copia
   
    def Hamming(self):
        ham=0
        for i in range(self.Size()):
            for j in range(self.Size()):
                if self.tablero[i][j]!=self.tablerometa[i][j] and self.tablero[i][j]!=0:
                    ham=ham+1
        return ham

    def Manhattan(self):
        man=0
        for i in range(self.Size()):
            for j in range(self.Size()):
                if self.tablero[i][j]!=0:
                    x=(self.tablero[i][j]-1)/self.Size()
                    y=(self.tablero[i][j]-1)-self.Size()*x
                    man+=abs(x-i)+abs(y-j)
        return man

    def Print_tab(self):
        for i in self.tablero:
            print i
        print "\n"

    def Vecinos(self):
        vecinos=[]
        for i in range( self.Size()):
            for j in range(self.Size()):
                if self.tablero[i][j]==0:
                    if i+1<self.Size():
                        vecinos.append((i+1,j))
                    if j+1<self.Size():
                        vecinos.append((i,j+1))
                    if i-1>=0:
                        vecinos.append((i-1,j))
                    if j-1>=0:
                        vecinos.append((i,j-1))
        return vecinos

    def Pos0(self):
        for i in range (self.Size()):
            for j in range(self.Size()):
                if self.tablero[i][j]==0:
                    posx0,posy0=j,i
        return posx0,posy0
   
    def ModificarPos0(self,b,a):
        posx0,posy0=self.Pos0()
        self.tablero[posy0][posx0]=self.tablero[b][a]
        self.tablero[b][a]= 0
       
    def Solucionado(self):
        if self.Manhattan()+self.Hamming() ==0:
            return True
               
class Resolver():

    def __init__(self,Tableroin):
        self.tablero=Tablero(Tableroin.Copia())
        self.movimientos=0
        self.estadoactual=Tablero(Tableroin.Copia())
        self.estadoanterior=(None,0)
        self.posiblesmov=queue.PriorityQueue()
        self.Repetidos=[]

    def Movimientos(self,vecinos):
        for i in range (len(vecinos)):
            posyv,posxv=vecinos[i]
            self.estadoactual.ModificarPos0(posyv,posxv)
            self.posiblesmov.put((self.estadoactual.Manhattan()+self.estadoactual.Hamming(),self.estadoactual))
            self.estadoactual=Tablero(self.tablero.Copia())
                       
    def Solucion(self):
        cont=0
        vecinos=self.tablero.Vecinos()[:]
        if self.tablero.EsSolucion():
            while(not(self.tablero.Solucionado())):
                self.Movimientos(vecinos)
                pos0x,pos0y=self.tablero.Pos0()
                self.tablero = Tablero(self.posiblesmov.get()[1].Copia())              
                if(self.tablero in self.Repetidos):
                    self.tablero = Tablero(self.posiblesmov.get()[1].Copia())
                else:
                    self.Repetidos.append(Tablero(self.tablero.Copia()))
                self.estadoactual = Tablero(self.tablero.Copia())
                self.posiblesmov=queue.PriorityQueue()
                vecinos=self.tablero.Vecinos()[:]
                vecinos.remove((pos0y,pos0x))
                cont=cont+1
                self.tablero.Print_tab()
            print "Cantidad de Movimientos",cont
        else:
            print "No es solucionable"

               
m=[]
print "Digite el tamanio del tablero (Dimensiones Iguales)"
x=int(raw_input("m*m "))
for i in range(x):
    m.append([])
    for j in range(x):
        print "Digite la posicion",i+1,j+1
        a=int(raw_input())
        m[i].append(a)
       
b= Tablero(m)
b.EsSolucion()
print "Tablero a resolver:"
b.Print_tab()
print "Solucion"
c=Resolver(b)
c.Solucion()