Existem duas maneiras de resolver um 15-puzzle. Uma é aquela a que todos os jogadores acabam por chegar — resolver a linha de cima, depois a coluna da esquerda, e recorrer. A outra é a forma como os computadores o fazem: uma busca heurística por milhões de estados, guiada por uma estimativa inferior inteligente de quantos movimentos faltam.
Este guia cobre ambas, mais ou menos pela ordem em que se aprendem.
O 15-puzzle, num parágrafo
Um tabuleiro 4×4, quinze peças numeradas, um espaço vazio. Faz-se deslizar as peças para o espaço vazio até os números ficarem em ordem — de 1 a 15, com o vazio no canto inferior direito. O tabuleiro foi inventado por Noyes Chapman em 1874 e tornou-se uma febre internacional na década de 1880, depois de Sam Loyd ter oferecido 1000 dólares pela resolução de uma variante insolúvel. É, no fundo, o mesmo puzzle do 8-puzzle — apenas com uma linha e uma coluna a mais.
Resolver à mão: o método de linhas e colunas
A técnica a que todo o ser humano acaba por chegar é esta:
- Resolva a linha 1. Coloque o 1 e o 2. Depois coloque o 3 no canto superior direito. A manobra em "L" — trazer o 4 para a posição do 3, deslizar o 3 por baixo, e depois rodar o par para o canto — é o truque que torna os cantos possíveis.
- Resolva a coluna 1. Coloque o 5, depois o 9 e depois o 13 no canto inferior esquerdo, usando a mesma manobra em L.
- Recursão. O que sobra é um subpuzzle 3×3 (com a coluna e a linha inferior direitas), que é apenas um 8-puzzle que já sabe resolver.
Um jogador confiante resolve um 15-puzzle em 3–5 minutos à mão. Um jogador novo pode demorar 20 minutos da primeira vez e um terço disso à terceira.
O mesmo método escala para 5×5 e 6×6. A recursão acaba sempre num endgame 3×3.
Solver ótimo: A* com distância de Manhattan
Um computador consegue muito melhor do que o método de linhas e colunas. Mais concretamente: consegue encontrar a solução mais curta, que raramente é a que um humano joga.
O facto matemático: o 15-puzzle mediano exige cerca de 52 movimentos quando resolvido de forma ótima. O pior caso é 80. O método de linhas e colunas usa tipicamente 100–150 movimentos no mesmo tabuleiro.
Para encontrar uma solução ótima, a busca A* trata cada estado do tabuleiro como um nó, cada movimento como uma aresta, e pergunta: quantos movimentos até ao objetivo, no mínimo? O número mínimo de movimentos restantes é impossível de calcular exatamente sem resolver o puzzle, mas um bom limite inferior torna o A* rápido.
O limite inferior clássico é a distância de Manhattan:
Para cada peça, some a distância em linhas e em colunas da sua posição atual até à sua posição-alvo. (Ignore o vazio.)
A distância de Manhattan é admissível — nunca superestima a distância verdadeira, porque cada peça tem mesmo de percorrer pelo menos essa distância. Com A* e Manhattan, o 8-puzzle resolve-se em microssegundos e o 15-puzzle em segundos.
IDA*: o primo amigável da memória
O A* tem de se lembrar de todos os estados que explorou. Para 15-puzzles, isso atinge centenas de megabytes de RAM nos tabuleiros mais difíceis. O A com aprofundamento iterativo (IDA)** troca memória por tempo, fazendo DFS com limite de profundidade usando a heurística e subindo o limite a cada ronda.
O IDA* é o que todos os solvers de referência usam de facto para o 15-puzzle. O artigo de Richard Korf de 1985 introduziu-o precisamente para resolver 15-puzzles de forma ótima no hardware do início dos anos 1980.
Para além de Manhattan: walking distance e bases de padrões
A distância de Manhattan é rápida mas folgada. Assume que as peças podem atravessar-se livremente. Não podem — duas peças na mesma linha têm de se alternar, o que custa movimentos extra.
A walking distance conta esses movimentos extra. Pré-computa-se, para cada par de linhas, o número mínimo de "trocas de linha" necessárias para permutar as peças nas linhas corretas. O mesmo para colunas. Soma-se. O resultado é comprovadamente mais apertado do que a distância de Manhattan — tipicamente cerca de 25% superior, o que significa que A*/IDA* explora menos 25% de nós.
A heurística mais forte conhecida para o 15-puzzle é a base de padrões aditiva disjunta:
- Particione as peças em grupos disjuntos (uma divisão comum é 5-5-5 mais o vazio).
- Para cada grupo, pré-compute, para cada disposição possível das peças desse grupo no tabuleiro, o número mínimo de movimentos para colocar essas peças nas suas posições-alvo, ignorando todas as outras.
- No momento da busca, some as consultas de cada grupo.
Uma partição 7+8 para o 15-puzzle ocupa cerca de 1 GB mas permite ao IDA* resolver qualquer 15-puzzle em milissegundos. Para o 24-puzzle (5×5), as bases de padrões são essencialmente a única abordagem prática.
Por que resolver à mão costuma ser mais rápido (para um puzzle)
Uma pequena verificação de realidade: escrever uma implementação de A*, escolher uma heurística e esperar que corra demora mais do que pegar num único 15-puzzle e resolvê-lo à mão. A matemática é interessante; a prática é que quem conhece o método de linhas e colunas resolve qualquer tabuleiro em cinco minutos certos.
A razão pela qual os solvers importam é o agregado: artigos de pesquisa que comparam heurísticas em milhares de instâncias aleatórias, manuais de IA que usam o 15-puzzle como benchmark, e apps que precisam de gerar puzzles garantidamente solúveis em cerca de N movimentos para calibração de dificuldade.
Ordem de leitura sugerida
Se chegou aqui à procura de escrever um solver, comece com A*/Manhattan, veja-o resolver alguns 8-puzzles e depois passe para IDA* nos 15-puzzles. Depois disso, a walking distance é um acréscimo de 100 linhas que duplica a velocidade. As bases de padrões são um projeto de fim de semana que dá mais uma ordem de grandeza.
Se chegou aqui à procura de jogar um 15-puzzle, aprenda primeiro o método de linhas e colunas, depois leia por que alguns tabuleiros são insolúveis, e só depois volte aqui para a teoria.