Se está a implementar um solver de quebra-cabeças deslizantes e não sabe que algoritmo usar, este artigo compara seis bem conhecidos quanto a velocidade, memória, complexidade de código e o tamanho de tabuleiro que tratam confortavelmente. As respostas são diferentes para o 3×3, o 4×4 e o 5×5.
1. Busca em largura (BFS)
O algoritmo correto mais simplório. Explorar estados nível a nível até encontrar o objetivo.
- Tempo — exponencial na profundidade da solução. Para o 8-puzzle termina numa fração de segundo. Para o 15-puzzle, não termina antes de o computador ficar sem RAM.
- Memória — guarda todo o conjunto visitado em memória. Dezenas de milhões de estados em 15-puzzles difíceis.
- Complexidade de código — vinte linhas.
- Veredicto — bom para o 3×3, inútil além disso.
2. A* com distância de Manhattan
O primeiro algoritmo a sério. Mesma estrutura do BFS, mas os estados são retirados de uma fila de prioridade ordenada por f = g + h, onde h é a heurística da distância de Manhattan.
- Tempo — milissegundos para o 8-puzzle, segundos a minutos para o 15-puzzle.
- Memória — continua a guardar tudo o que explorou em memória; tratável para o 8, doloroso para o 15.
- Complexidade de código — cinquenta linhas, sobretudo encanamento da fila de prioridade.
- Veredicto — a ferramenta certa para o 8-puzzle. Borderline para o 15.
3. A* com Manhattan + conflito linear
Adicionar 2 movimentos à heurística por cada par de peças na mesma linha que estejam ambas na sua linha-alvo mas pela ordem errada (analogamente para colunas). Vão ter de se passar uma à outra, coisa que a distância de Manhattan não vê.
- Tempo — tipicamente 5–15% mais rápido do que A* com Manhattan puro.
- Memória — inalterada.
- Complexidade de código — sessenta linhas.
- Veredicto — estritamente melhor do que A* com Manhattan puro. Use sempre.
4. IDA* com Manhattan + conflito linear
A* com aprofundamento iterativo. Fazer DFS com limite de profundidade usando o f-custo como medida, subindo o limite a cada iteração. Troca memória por tempo através de re-exploração.
- Tempo — ligeiramente mais lento por nó do que o A* devido à exploração repetida, mas a menor pressão de memória costuma vencer em 15-puzzles difíceis.
- Memória — O(profundidade), não O(estados explorados). É a vitória.
- Complexidade de código — oitenta linhas (DFS recursivo, gestão de limiar).
- Veredicto — a ferramenta certa para o 4×4. O padrão desde Korf 1985.
5. IDA* com walking distance
A walking distance é uma heurística mais apertada. Pré-computa-se, para cada disposição de peças projetada apenas em linhas, o número mínimo de operações de troca de linha para colocar cada peça na linha correta. O mesmo para colunas. Soma-se.
Capta uma coisa que Manhattan não vê: peças na mesma linha a "brigar" pelo mesmo lugar.
- Tempo — tipicamente 2× mais rápido do que Manhattan + conflito linear em 15-puzzles difíceis, porque a heurística é mais apertada, pelo que o IDA* poda mais.
- Memória — acrescenta uma pequena tabela pré-computada (~500 KB para um 4×4).
- Complexidade de código — 150 linhas. O pré-cálculo é um BFS num espaço de estados reduzido.
- Veredicto — a ferramenta certa para o 4×4 se tiver orçamento de engenharia. A primeira melhoria não-trivial.
6. IDA* com bases de padrões aditivas disjuntas
A heurística mais forte conhecida para quebra-cabeças deslizantes. Particione as peças em grupos disjuntos (uma partição comum do 15-puzzle é 7+8, ou 5+5+5). Pré-compute, para cada grupo, o custo de permutar as peças do grupo para as suas posições-alvo sobre todas as disposições possíveis desse grupo. No momento da busca, consulta-se a contribuição de cada grupo e soma-se.
- Tempo — resolve o 15-puzzle mais difícil em milissegundos. Resolve 24-puzzles aleatórios em segundos.
- Memória — significativa. Uma partição 7+8 para o 15-puzzle tem cerca de 1 GB. Uma partição 5+5+5+9 para o 24-puzzle tem cerca de 4 GB. A memória domina a engenharia.
- Complexidade de código — 300+ linhas. O passo de pré-cálculo usa BFS retrógrado no espaço de estados do grupo e é o grosso do trabalho.
- Veredicto — a ferramenta certa para 5×5 e 6×6. Exagerada para o 3×3.
Recomendações-resumo
Se está a escrever hoje um solver:
- Para o 3×3, use A* com Manhattan + conflito linear. Qualquer coisa mais é sobre-engenharia.
- Para o 4×4, use IDA* com walking distance. As bases de padrões dão ganhos marginais a este tamanho; a complexidade de engenharia não compensa.
- Para o 5×5, use IDA* com bases de padrões aditivas (5+5+5+9 é padrão). Sem bases de padrões vai expirar nas instâncias mais difíceis.
- Para o 6×6 (o 35-puzzle), os mesmos algoritmos resolvem instâncias aleatórias, mas os piores casos continuam a ser questão de pesquisa. A maioria das apps não tenta.
E aprendizagem automática?
Pergunta razoável em 2026. Heurísticas por redes neuronais são estudadas pelo menos desde 2014 e conseguem produzir heurísticas rápidas para quebra-cabeças deslizantes. O problema é que tipicamente não são admissíveis — podem superestimar, o que significa que o algoritmo resultante deixa de ter garantia de otimalidade. Para quem desenvolve apps que querem soluções garantidamente ótimas para a calibração de dificuldade, as bases de padrões clássicas continuam a ser a ferramenta certa.
Para interesse de pesquisa, bases de padrões treinadas por uma rede neuronal produzem ligeiros ganhos de velocidade nas instâncias mais difíceis do 15-puzzle. Útil para artigos académicos, marginal para software em produção.
O que vai numa app real
Uma app móvel em produção que precise de um solver para geração de dicas quase sempre acaba em:
- IDA* + walking distance para o 4×4.
- IDA* + uma pequena base de padrões para o 5×5.
- Uma única chamada apenas-para-o-próximo-movimento a partir do botão de dica.
- Tudo corre no aparelho. O solver inteiro são algumas centenas de kilobytes de código mais alguns megabytes de tabelas pré-computadas.
É a stack pragmática certa para uma app calma de telemóvel. O botão de dica do Slide Puzzle funciona exatamente assim.