from aigyminsper.search.search_algorithms import AEstrela
from aigyminsper.search.graph import State
import math
class Puzzle8(State):
objetivo = [[1,2,3],[8,0,4],[7,6,5]]
def __init__(self, tabuleiro, op):
"""Inicializa o tabuleiro e o movimento que o produziu.
tabuleiro: uma matriz quadrada que representa a posição de cada peça
ex: [[2, 1, 3],
[0, 8, 4]
[6, 5, 7]]
observação: 0 representa o espaço vazio.
op: operação que levou ao estado atual
"""
super().__init__(op)
self.tabuleiro = tabuleiro
@staticmethod
def find_number(board, number):
"""Encontra a linha e a coluna que contêm uma peça."""
for i in range(0,3):
for j in range(0,3):
if board[i][j] == number:
return i, j
def copy_board(self):
"""Cria uma cópia do tabuleiro."""
resultado = [[0,0,0],[0,0,0],[0,0,0]]
for i in range(0,3):
for j in range(0,3):
resultado[i][j] = self.tabuleiro[i][j]
return resultado
def successors(self):
"""Retorna cada tabuleiro produzido por um movimento válido do vazio."""
sucessors = []
lin, col = Puzzle8.find_number(self.tabuleiro, 0)
# Move o espaço vazio para cima
if lin > 0 and self.operator != 'baixo':
novo = self.copy_board()
temp = self.tabuleiro[lin-1][col]
novo[lin][col] = temp
novo[lin-1][col] = 0
sucessors.append(Puzzle8(novo,'cima'))
# Move o espaço vazio para baixo
if lin < 2 and self.operator != 'cima':
novo = self.copy_board()
temp = self.tabuleiro[lin+1][col]
novo[lin][col] = temp
novo[lin+1][col] = 0
sucessors.append(Puzzle8(novo,"baixo"))
# Move o espaço vazio para a esquerda
if col > 0 and self.operator != 'direita':
novo = self.copy_board()
temp = self.tabuleiro[lin][col-1]
novo[lin][col] = temp
novo[lin][col-1] = 0
sucessors.append(Puzzle8(novo,"esquerda"))
# Move o espaço vazio para a direita
if col < 2 and self.operator != 'esquerda':
novo = self.copy_board()
temp = self.tabuleiro[lin][col+1]
novo[lin][col] = temp
novo[lin][col+1] = 0
sucessors.append(Puzzle8(novo,"direita"))
return sucessors
def is_goal(self):
"""Retorna se o tabuleiro corresponde à configuração objetivo.
tabuleiro = [[1,2,3],
[8,0,4],
[7,6,5]]
"""
for i in range(0,3):
for j in range(0,3):
if self.tabuleiro[i][j] != self.objetivo[i][j]:
return False
return True
def description(self):
"""Descreve o problema representado."""
return "8 Puzzle"
def cost(self):
"""Atribui custo unitário a cada movimento do espaço vazio."""
return 1
def env(self):
"""Identifica o estado pela configuração do tabuleiro."""
return str(self.tabuleiro)
def h(self):
"""Estima a distância usando a heurística selecionada."""
return self.misplaced_tiles()
#return self.euclidean_distance()
#
# Quantidade de peças fora do lugar
#
def misplaced_tiles(self):
"""Conta as peças que estão fora de suas posições objetivo."""
count = 0
if self.tabuleiro[0][0] != 1:
count = count + 1
if self.tabuleiro[0][1] != 2:
count = count + 1
if self.tabuleiro[0][2] != 3:
count = count + 1
if self.tabuleiro[1][0] != 8:
count = count + 1
if self.tabuleiro[1][1] != 0:
count = count + 1
if self.tabuleiro[1][2] != 4:
count = count + 1
if self.tabuleiro[2][0] != 7:
count = count + 1
if self.tabuleiro[2][1] != 6:
count = count + 1
if self.tabuleiro[2][2] != 5:
count = count + 1
return count
#
# Distância euclidiana
#
def euclidean_distance(self):
"""Soma a distância em linha reta de cada peça até o objetivo."""
count = 0
for num in range(0,8):
lin_ideal, col_ideal = Puzzle8.find_number(self.objetivo, num)
lin_real, col_real = Puzzle8.find_number(self.tabuleiro, num)
count = count + math.sqrt((lin_ideal - lin_real)**2 + (col_ideal - col_real)**2)
return count
#
# Conta as inversões necessárias para ordenar a sequência numérica.
# Uma quantidade par é solucionável e uma quantidade ímpar não é.
#
# Referência: https://pt.stackoverflow.com/questions/333702/como-verificar-se-o-sliding-puzzle-%C3%A9-solucion%C3%A1vel
#
@staticmethod
def has_solution(board):
"""Retorna se o tabuleiro inicial fornecido possui solução."""
count = 0
lista = []
for lin in range(0,3):
for col in range(0,3):
if board[lin][col] != 0:
lista.append(board[lin][col])
for i in range(0,8):
for j in range(i+1,8):
if lista[i] > lista[j]:
count = count + 1
if count % 2:
return True
else:
return False
def show_path(self):
"""Resolve o quebra-cabeça com A* e retorna o caminho encontrado."""
algorithm = AEstrela()
if not Puzzle8.has_solution(self.tabuleiro):
return 'Nao tem solucao'
result = algorithm.search(self)
if result != None:
return result.show_path()
else:
return 'Nao achou solucao'
def main():
tabuleiro_trivial = [[1,2,3],[8,4,0],[7,6,5]]
tabuleiro_facil = [[8,1,3],[0,7,2],[6,5,4]]
tabuleiro_facil2 = [[8,1,3],[7,0,2],[6,5,4]]
tabuleiro_facil3 = [[0,1,3],[8,7,2],[6,5,4]]
tabuleiro_dificil1 = [[7,8,6],[2,3,5],[1,4,0]]
tabuleiro_dificil2 = [[7,8,6],[2,3,5],[0,1,4]]
tabuleiro_dificil3 = [[8,3,6],[7,5,4],[2,1,0]]
tabuleiro_dificil4 = [[3,1,2],[5,4,8],[0,6,7]]
tabuleiro_impossivel1 = [[3,4,8],[1,2,5],[7,0,6]]
tabuleiro_impossivel2 = [[5,4,0],[6,1,8],[7,3,2]]
tabuleiro_impossivel3 = [[1,7,2],[3,9,5],[6,4,8]]
state = Puzzle8(tabuleiro_facil3,'')
print(state.show_path())
if __name__ == '__main__':
main()