O 8-puzzle é o primeiro programa que se escreve no dia em que se aprende busca heurística. É pequeno o suficiente para que quase qualquer abordagem funcione, e grande o suficiente para que as abordagens más sejam visivelmente piores do que as boas. Este artigo percorre a solução-padrão de cima a baixo.
O estado
Represente o tabuleiro como um array de nove inteiros, indexados 0..8 por ordem de linhas:
posições: índices:
1 2 3 0 1 2
4 5 6 ←→ 3 4 5
7 8 _ 6 7 8
A célula vazia tem um valor sentinela — 0 é a escolha habitual. O estado-objetivo é [1, 2, 3, 4, 5, 6, 7, 8, 0].
Os movimentos
A partir de uma posição com o vazio no índice e, pode trocar o vazio com os seus vizinhos ortogonais: e-3 (acima) se não estiver na linha de cima, e+3 (abaixo) se não estiver na linha de baixo, e-1 (à esquerda) se não estiver na coluna mais à esquerda, e+1 (à direita) se não estiver na coluna mais à direita.
Uma função neighbors(state) devolve até quatro estados alcançáveis num movimento.
A heurística: distância de Manhattan
Para cada peça (ignore o vazio), calcule a distância em linha mais a distância em coluna entre a sua posição atual e a posição-alvo. Some por todas as peças. Essa soma é um limite inferior do número de movimentos restantes — cada peça tem mesmo de percorrer pelo menos essa distância.
Em pseudocódigo:
h(state) = soma sobre peças t:
abs(row(current) - row(goal)) + abs(col(current) - col(goal))
A distância de Manhattan é admissível (nunca superestima) e consistente (satisfaz a desigualdade triangular). Ambas as propriedades importam para o A*.
A* em doze linhas
O A* mantém uma fila de prioridade de estados, ordenada por f = g + h, onde g é a profundidade (movimentos feitos até agora) e h é a estimativa heurística dos movimentos restantes. A cada iteração: retira o estado com menor f, expande-o, empurra os vizinhos com o f atualizado.
open = priority_queue()
open.push(start, f=h(start))
came_from = {}; g = {start: 0}
while open is not empty:
state = open.pop()
if state == goal: return reconstruct_path(came_from, state)
for n in neighbors(state):
tentative_g = g[state] + 1
if n not in g or tentative_g < g[n]:
g[n] = tentative_g
came_from[n] = state
open.push(n, f=tentative_g + h(n))
É este o solver inteiro. Implemente h, implemente neighbors, e pode resolver qualquer 8-puzzle.
Desempenho
O A* com distância de Manhattan resolve qualquer 8-puzzle em algumas centenas de microssegundos, expandindo algumas centenas a alguns milhares de estados nas instâncias mais difíceis. O espaço de estados é pequeno o suficiente para que o A* domine o IDA* neste tamanho — A* é a escolha certa para o 3×3, IDA* assume a partir do 4×4.
Armadilhas comuns
Três coisas que vai errar à primeira tentativa:
Hash do estado. Os tuplos em Python têm hash naturalmente; arrays de int em Java não. Em qualquer linguagem que use, o estado precisa de ser hashable para que os conjuntos aberto/fechado funcionem. Um truque comum é codificar o estado de 9 peças como um único inteiro de 32 bits (4 bits por célula, dado que as células são 0..8).
Esquecer o teste de paridade das inversões. Se gerar um 8-puzzle aleatório baralhando, metade das vezes o puzzle é insolúvel e o A* irá explorar todo o meio-espaço de 181 440 estados à procura de um caminho que não existe. Acrescente um teste rápido de paridade antes de correr o A*, ou gere caminhando para trás a partir do objetivo.
Tratar o vazio como peça na heurística. A distância de Manhattan é somada apenas sobre as peças reais. Incluir o vazio infla a heurística e quebra a admissibilidade (pode "consertar" o vazio de graça com um movimento).
Para além de Manhattan
Pode fazer melhor do que Manhattan no 8-puzzle, mas não muito:
- Conflito linear — se duas peças na mesma linha estiverem ambas na sua linha-alvo mas pela ordem errada, vão precisar de pelo menos dois movimentos extra para se passar. Adicione 2 por conflito. Melhora Manhattan em 5–15%.
- Bases de padrões — pré-computar o custo ótimo sobre subconjuntos de peças. Custo de memória enorme para um ganho de velocidade minúsculo no 8-puzzle. Vale a pena para solvers do 15-puzzle, não aqui.
Para 8-puzzles, Manhattan simples com conflito linear é o ponto ideal prático.
O que construir a seguir
Se escreveu um solver para o 8-puzzle, as extensões naturais são:
- Solver do 15-puzzle com IDA* + walking distance. As mesmas ideias básicas, busca mais profunda. (Guia aqui.)
- Solver geral de N-puzzle com bases de padrões. Um projeto de fim de semana.
- Teste de solubilidade — uma função de 30 linhas que devolve true se um tabuleiro for alcançável a partir do objetivo. Útil para o desenvolvimento de apps. (Baseado no teorema da paridade.)
O 8-puzzle é pequeno. As técnicas que se aprendem a resolvê-lo escalam até ao topo.