blog.patrulleros.com.br

8 Puzzle - Parte 2

18 de Fevereiro de 2009 às 12:29 Thiago  | Enviar por e-mail Hits para esta publicação: 967

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

Publicação arquivada em: Tecnologia

Enviar por e-mail | Hits para esta publicação: 968