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):
"""Initialize the puzzle board and the move that produced it.
tabuleiro: A square array representing the position of every tile
ex: [[2, 1, 3],
[0, 8, 4]
[6, 5, 7]]
note: 0 represents the empty space.
op: the operation that led to the current state
"""
super().__init__(op)
self.tabuleiro = tabuleiro
@staticmethod
def find_number(board, number):
"""Find the row and column containing a tile."""
for i in range(0,3):
for j in range(0,3):
if board[i][j] == number:
return i, j
def copy_board(self):
"""Create a copy of the board."""
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):
"""Return every board produced by a valid empty-space movement."""
sucessors = []
lin, col = Puzzle8.find_number(self.tabuleiro, 0)
# Move the empty space up
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 the empty space down
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 the empty space left
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 the empty space right
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):
"""Return whether the board matches the target configuration.
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):
"""Describe the represented problem."""
return "8 Puzzle"
def cost(self):
"""Assign unit cost to every empty-space movement."""
return 1
def env(self):
"""Identify the state from its board configuration."""
return str(self.tabuleiro)
def h(self):
"""Estimate distance using the selected puzzle heuristic."""
return self.misplaced_tiles()
#return self.euclidean_distance()
#
# Number of misplaced tiles
#
def misplaced_tiles(self):
"""Count tiles that are outside their target positions."""
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
#
# Euclidean distance
#
def euclidean_distance(self):
"""Sum each tile's straight-line distance from its target."""
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
#
# Count the inversions required to order the numerical sequence.
# An even count is solvable and an odd count is unsolvable.
#
# Reference: https://pt.stackoverflow.com/questions/333702/como-verificar-se-o-sliding-puzzle-%C3%A9-solucion%C3%A1vel
#
@staticmethod
def has_solution(board):
"""Return whether the given initial board has a solution."""
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):
"""Solve the puzzle with A* and return the resulting path."""
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()