# Como resolver o slide puzzle-15 usando backtracking?

+1 voto
582 visitas

Resolva o slide puzzle-15 usando backtracking. Discuta a sua solucao para o problema.

## 1 Resposta

+1 voto
respondida Mai 31, 2016 por (21 pontos)

import pprint
pp = pprint.PrettyPrinter(indent=4)

expandido = []
nosExpandidos=0
while nivel:
i = 0
for j in range(1, len(nivel)):
if nivel[i][0] > nivel[j][0]:
i = j
caminho = nivel[i]
nivel = nivel[:i] + nivel[i+1:]
noFinal = caminho[-1]
if noFinal == objetivo:
break
if noFinal in expandido: continue
for k in mover(noFinal):
if k in expandido: continue
novoCaminho = [caminho[0] + heuristica(k) - heuristica(noFinal)] + caminho[1:] + [k]
nivel.append(novoCaminho)
expandido.append(noFinal)
nosExpandidos += 1
print "Total de nós expandidos:", nosExpandidos
print "Solução:"
pp.pprint(caminho)

def heuristica(puzzle):
distanciaManhattanTotal = 0
m = eval(puzzle)
for i in range(4):
for j in range(4):
if m[i][j] == 0: continue
distanciaManhattanTotal += abs(i - (m[i][j]/4)) + abs(j -  (m[i][j]%4));
return distanciaManhattanTotal

def mover(puzzle):
listaMovimentos = []
m = eval(puzzle)
i = 0
while 0 not in m[i]: i += 1
j = m[i].index(0);
if i > 0:
m[i][j], m[i-1][j] = m[i-1][j], m[i][j];
listaMovimentos.append(str(m))
m[i][j], m[i-1][j] = m[i-1][j], m[i][j];
if i < 3:
m[i][j], m[i+1][j] = m[i+1][j], m[i][j]
listaMovimentos.append(str(m))
m[i][j], m[i+1][j] = m[i+1][j], m[i][j]
if j > 0:
m[i][j], m[i][j-1] = m[i][j-1], m[i][j]
listaMovimentos.append(str(m))
m[i][j], m[i][j-1] = m[i][j-1], m[i][j]
if j < 3:
m[i][j], m[i][j+1] = m[i][j+1], m[i][j]
listaMovimentos.append(str(m))
m[i][j], m[i][j+1] = m[i][j+1], m[i][j]
return listaMovimentos

if __name__ == '__main__':
estadoAtual = str([[1, 2, 6, 3],[4, 9, 5, 8], [7, 13, 11, 15],[12, 14, 0, 10]])
objetivo = str([[0, 1, 2, 3],[4, 5, 6, 7], [8, 9, 10, 11],[12, 13, 14, 15]])