O 15-puzzle é um benchmark para algoritmos de busca em IA desde os anos 1960. Cada geração de algoritmo foi inventada para ultrapassar o muro em que a anterior bateu. Este artigo percorre-os por ordem de invenção, com aquilo em que cada um se destacava e o que tornou o seguinte necessário.
Anos 1960 — busca em largura
O primeiro algoritmo que qualquer pessoa tenta. Explora os estados nível a nível: a profundidade 1 tem 4 estados, a 2 tem 16, a 3 tem 64, e assim por diante. Continue a explorar até encontrar o objetivo.
Para o 8-puzzle, o BFS termina rapidamente — a profundidade do pior caso é 31, portanto no máximo 4³¹ estados (muito menos na prática devido a revisitações). Para o 15-puzzle, a profundidade mais difícil é 80, ou seja, 4⁸⁰ estados. Isso é mais estados do que átomos no universo observável. O BFS não termina.
O muro: explosão exponencial. Resolver por busca não informada é impraticável além do 3×3.
1968 — busca A*
Hart, Nilsson e Raphael publicam A Formal Basis for the Heuristic Determination of Minimum Cost Paths. A ideia: em vez de explorar estados em ordem de distância ao início, explorar em ordem de f = g + h, onde h é uma estimativa inferior da distância restante.
Para o 15-puzzle, h é a distância de Manhattan — soma das distâncias em linha e coluna de cada peça à sua posição-alvo. Manhattan é admissível (nunca superestima) e consistente (satisfaz uma desigualdade triangular). Com estas propriedades, o A* encontra a solução ótima.
Desempenho no 15-puzzle: resolve qualquer tabuleiro, mas nas instâncias mais difíceis explora milhões de estados e consome centenas de megabytes de memória. O muro: memória.
1985 — IDA*
Depth-first iterative-deepening: An optimal admissible tree search, de Richard Korf. A intuição: em vez da fila de prioridade do A* (que guarda todos os estados explorados), fazer DFS com aprofundamento iterativo onde o limite de profundidade é o f-custo em vez da profundidade.
O IDA* explora os mesmos estados que o A* exploraria, aproximadamente na mesma ordem, mas sem se lembrar deles entre iterações. Cada "varrimento em profundidade" usa O(profundidade) de memória em vez de O(estados explorados).
Desempenho no 15-puzzle: resolve qualquer tabuleiro em segundos no hardware de 1985, cabe em kilobytes de memória. O muro: a heurística continua a ser Manhattan. Acelerar a busca exige uma heurística mais apertada.
Anos 1990 — conflito linear
Criticizing solutions to relaxed models yields powerful admissible heuristics, de Hansson, Mayer e Yung. A heurística de Manhattan assume que as peças podem passar umas pelas outras. Não podem.
O conflito linear acrescenta 2 movimentos à heurística por cada par de peças na mesma linha, ambas pertencentes a essa linha, mas na ordem errada — uma delas terá de sair da linha para deixar a outra passar. O mesmo vale para colunas.
Efeito: tipicamente uma redução de 5–15% nos nós expandidos em 15-puzzles difíceis. Melhoria estrita sobre Manhattan puro; sem desvantagem real.
1996 — walking distance
Uma heurística que captura mais profundamente a estrutura do puzzle. Para cada disposição de peças projetada apenas em linhas (ignorando posições dentro da linha), pré-computa-se o número mínimo de operações de troca de linha para colocar cada peça na sua linha correta. O mesmo para colunas.
A walking distance é admissível e consideravelmente mais apertada do que Manhattan + conflito linear — tipicamente 1,5–2× o valor de Manhattan, o que significa que o IDA* expande muito menos nós.
Custo de implementação: uma pequena tabela pré-computada (~500 KB para um 4×4). Ponto ideal para o 15-puzzle.
2002 — bases de padrões aditivas disjuntas
Disjoint pattern database heuristics, de Korf e Felner. A heurística mais forte conhecida para quebra-cabeças deslizantes.
A ideia: particionar as peças em grupos disjuntos (uma partição 7+8 para o 15-puzzle é padrão). Para cada grupo, pré-computar o custo ótimo de levar apenas as peças desse grupo às suas posições-alvo, ignorando todas as outras. Tabular todas as disposições possíveis do grupo.
No momento da busca, consulta-se a contribuição de cada grupo e soma-se. Como os grupos são disjuntos e os movimentos necessários a cada grupo não conflitam (sujeito a um argumento cuidadoso), a soma é admissível.
Custo de memória: cerca de 1 GB para o 15-puzzle. Desempenho: resolve o 15-puzzle mais difícil em alguns milhares de expansões de nó — milissegundos.
2005+ — bases de padrões maiores para puzzles maiores
A mesma técnica escala para o 24-puzzle (5×5) e além. Uma partição 5+5+5+9 para o 24-puzzle ocupa cerca de 4 GB. Com ela, qualquer 24-puzzle aleatório resolve-se em segundos.
O 35-puzzle (6×6) está no limite do tratável. As instâncias 6×6 mais difíceis continuam a ser objeto de pesquisa em 2026.
Anos 2010+ — heurísticas por redes neuronais
Redes neuronais foram treinadas para prever a quantidade tipo distância-de-Manhattan para quebra-cabeças deslizantes, por vezes produzindo heurísticas mais apertadas do que as feitas à mão. O senão: as heurísticas neuronais geralmente não são comprovadamente admissíveis, pelo que os solvers construídos sobre elas devolvem respostas provavelmente-ótimas em vez de garantidamente-ótimas.
Para artigos de pesquisa, isto é interessante. Para software em produção, onde a otimalidade importa (calibração de dificuldade em jogos), as bases de padrões clássicas continuam a ser a ferramenta certa.
Por que esta história importa
Cada onda de pesquisa em algoritmos de quebra-cabeças deslizantes foi motivada pela mesma pressão: o puzzle é pequeno o suficiente para algoritmos serem comparados, grande o suficiente para algoritmos maus expirarem. O 15-puzzle foi o campo de testes para avanços gerais em busca heurística — A*, IDA*, bases de padrões — que hoje alimentam planeamento de rotas, demonstração de teoremas e muitos outros domínios.
Quando resolve um 15-puzzle numa app usando um botão de dica, está a usar algoritmos que foram desenvolvidos exatamente para este jogo e depois generalizados para todo o resto.
Uma tabela-resumo
| Ano | Algoritmo | Tempo para resolver 15-puzzle difícil | Memória | O que o tornou possível |
|---|---|---|---|---|
| Anos 1960 | BFS | Não termina | Enorme | — |
| 1968 | A* + Manhattan | Minutos | Centenas de MB | Busca heurística |
| 1985 | IDA* + Manhattan | Segundos | KB | Aprofundamento iterativo |
| 1996 | IDA* + walking distance | < 1 seg | + 500 KB pré-computados | Heurística melhor |
| 2002 | IDA* + base de padrões 7+8 | Milissegundos | + 1 GB pré-computado | Enumeração de subconjuntos |
Cada linha é um verdadeiro salto qualitativo, não uma melhoria marginal. A história da resolução do 15-puzzle é também a história da busca heurística moderna.