8 Puzzle - Parte 2
Ontem fiz um programa para resolver o 8 puzzle. Testei em casa com o puzzle presente no jogo Professor Layton e para minha tristeza o programa era lento demais. Deixei ligado por vários minutos e a resposta não apareceu. Logicamente precisava aumentar a performance e a maneira mais óbvia era trocar o algoritmo de busca, já que a busca em largura, apesar de dar a resposta correta, é muito lenta.
Dito isto, troquei para o algoritmo A*, que é o super bambambam dos algoritmos de busca. Para implementar este algoritmo, preciso de uma fila de prioridade e felizmente a biblioteca de Python já possui uma implementação no módulo heapq. Também é preciso associar um custo com cada configuração do tabuleiro e fiz da seguinte forma: o custo de um configuração é a soma da quantidade de movimentos até chegar nela mais a soma das distâncias Manhattan de cada quadrado até sua posição na configuração final. Usei uma matriz bacana para armazenar fácil essas distâncias, hehe!
Por fim, rodei o programa e dentro de poucos minutos ele deu uma resposta. Testei e a resposta está correta. Até que enfim resolvi esse puzzle terrível! O código está abaixo.
Yesterday I wrote a program to solve the 8 puzzle, but my implementation was too slow. I changed the search algorithm to A* and everyting worked just fine. I finally got through that pesky puzzle in the game.
"""
This is a solver for the 8 sliders puzzle.
A state is a snapshot of the game board. It is represented by a list of
9 items, eg. [0,1,2,3,4,5,6,7,8]. The positions in the list map to the
following positions on the board:
0 1 2
3 4 5
6 7 8
We assume the square labelled 0 is the empty square. It is possible
to have more of the same number on the board.
"""
# A Priority Queue implementation
import heapq
""" The allowed moves in the game. For example, 0:[1,3] means that
a square in position zero can be swapped with the square in position one
or the square in position three.
"""
SWAPS = {0:[1,3],
1:[0,2,4],
2:[1,5],
3:[0,4,6],
4:[1,3,5,7],
5:[2,4,8],
6:[3,7],
7:[4,6,8],
8:[5,7]}
def solve_eight_puzzle(begin, goal):
distance = calculate_distance(goal)
openlist = []
heapq.heappush(openlist, package_cost(begin, 0, distance))
closedlist = []
previous = {begin:None}
while len(openlist) > 0:
print len(openlist),
cost, state = heapq.heappop(openlist)
closedlist.append(state)
if state == goal:
s = goal
path = []
while previous[s] is not None:
path.append(s)
s = previous[s]
path.append(s)
path.reverse()
return path
nextstates = [s for s in possible_moves(state) if s not in closedlist]
for next in nextstates:
previous[next] = state
heapq.heappush(openlist, package_cost(next, cost + 1, distance))
return None
def package_cost(state, path_length, distance):
cost = path_length
for i in range(9):
cost += distance[state[i]][i]
return (cost, state)
def possible_moves(state):
izero = index_of_zero(state)
swaps = SWAPS[izero]
new_states = []
for swap in swaps:
new_state = list(state)
new_state[izero] = state[swap]
new_state[swap] = state[izero]
new_states.append(tuple(new_state))
return new_states
def instructions(state_list):
answer = []
previous = None
for state in state_list:
if previous is not None:
izero1 = index_of_zero(previous)
izero2 = index_of_zero(state)
if izero1 / 3 < izero2 / 3:
# zero went down
inst = "move a piece up"
elif izero1 / 3 == izero2 / 3:
if izero1 < izero2:
# zero went right
inst = "move a piece left"
else:
#zero went left
inst = "move a piece right"
elif izero1 / 3 > izero2 / 3:
# zero went up
inst = “move a piece down”
answer.append(inst)
previous = state
return answer
def index_of_zero(tup):
i = 0
while i < 9:
if tup[i] == 0:
return i
i += 1
print "Mega error: there is no ZERO in", tup
def calculate_distance(goal):
distance = {}
distance[goal[0]] = [0, 1, 2, 1, 2, 3, 2, 3, 4]
distance[goal[1]] = [1, 0, 1, 2, 1, 2, 3, 2, 3]
distance[goal[2]] = [2, 1, 0, 3, 2, 1, 4, 3, 2]
distance[goal[3]] = [1, 2, 3, 0, 1, 2, 1, 2, 3]
distance[goal[4]] = [2, 1, 2, 1, 0, 1, 2, 1, 2]
distance[goal[5]] = [3, 2, 1, 2, 1, 0, 3, 2, 1]
distance[goal[6]] = [2, 3, 4, 1, 2, 3, 0, 1, 2]
distance[goal[7]] = [3, 2, 3, 2, 1, 2, 1, 0, 1]
distance[goal[8]] = [4, 3, 2, 3, 2, 1, 2, 1, 0]
return distance
# Test
i = 1
print
for inst in instructions(solve_eight_puzzle((1,2,3,4,5,6,7,0,1),(1,2,3,4,0,7,6,5,1))):
print i, inst
i += 1
raw_input()
Adicionar comentário 18 de Fevereiro de 2009 às 12:29 Thiago
