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()
