blog.patrulleros.com.br

8 Puzzle

17 de Fevereiro de 2009 às 17:27 Thiago  | Enviar por e-mail Hits para esta publicação: 817

O problema 8 puzzle é um quebra cabeça em que temos um tabuleiro 3 por 3 com 8 quadrados deslizantes e um espaço em branco. Dada uma posição inicial dos quadrados, pede-se para chegar em uma outra posição qualquer considerando que:

• Os quadrados podem ser deslizados para ocuparem a posição previamente em branco.
• Movimentos diagonais são proibidos.
• As peças só podem ser deslizadas, isto é, não pode-se tirá-las do tabuleiro.

Estava jogando o ótimo Professor Layton and the Curious Village quando emperrei num dos puzzles, que é um 8 puzzle (Puzzle 107: A Worm’s Dream). Depois de milhares de movimentos, desisti e resolvi escrever um programa para resolver o problema para mim, hehe. Apresento a solução abaixo, escrita em Python 2.5.

Adotei a abordagem mais simples, é uma busca em largura sem heurística no grafo onde os vértices são as diversas configurações do tabuleiro. Primeiro implementei a busca como uma função recursiva, mas estava estourando a pilha (Stack Overflow) então reescrevi a função de forma iterativa.

Conseguem ver como ela funciona? O que pode ser feito para melhorar a performance?

Alguém tem uma idéia melhor para como armazenar a seqüência de movimentos que o jogador tem que fazer?

This Python 2.5 program solves the 8 puzzle. It uses a simple breadth first search algorithm in a graph where the vertices are game board snapshots.

Can you see how it works? How can the performance be improved? Does someone have a better idea of how the answer should be stored or presented?

"""
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.
"""

""" 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):
    openlist = [begin]
    closedlist = []
    previous = {tuple(begin):None}
    while len(openlist) > 0:
        state = openlist.pop(0)
        closedlist.append(state)
        if state == goal:
            s = tuple(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[tuple(next)] = tuple(state)
        openlist.extend(nextstates)
    return None

def possible_moves(state):
    izero = state.index(0)
    swaps = SWAPS[izero]
    new_states = []
    for swap in swaps:
        new_state = state[:]
        new_state[izero] = state[swap]
        new_state[swap] = state[izero]
        new_states.append(new_state)
    return new_states

# Test
print solve_eight_puzzle([0,1,3,4,2,5,7,8,6],[1,2,3,4,5,6,7,8,0])

Publicação arquivada em: Tecnologia

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