Um solver de quebra-cabeça deslizante é um programa que, dada qualquer posição inicial solúvel, devolve uma sequência de movimentos que leva ao objetivo. É o tipo de ferramenta com dois públicos: jogadores que estão presos, e quem precisa de lançar uma app de quebra-cabeças deslizantes.
Os dois públicos querem coisas muito diferentes.
Por que os jogadores quase nunca precisam de um solver
Se está preso num quebra-cabeça deslizante, a solução honesta normalmente não é "correr um solver". É uma destas três:
- Aprender o método de linhas e colunas. A maior parte dos jogadores que desistem é dos que nunca aprenderam a estratégia canónica. (Comece pelo 8-puzzle e suba depois.)
- Verificar que o puzzle é solúvel. Se não consegue encontrar solução faça o que fizer, a app pode ter gerado um tabuleiro insolúvel por engano. Verifica-se depressa.
- Usar uma dica, não uma resolução completa. O próximo movimento costuma chegar para o desencravar. As apps que oferecem dicas (a nossa, no Premium) calculam habitualmente um movimento sob demanda, não a solução inteira.
Uma solução completa raramente lhe ensina algo útil, porque o solver produz uma sequência ótima — habitualmente 52 movimentos para um 15-puzzle difícil — e ver 52 movimentos ótimos passarem a correr no telemóvel não constrói intuição.
A dica é a unidade certa. Se precisa de uma dica, não precisa de um solver.
Por que quem desenvolve precisa sempre de um
Construir uma app de quebra-cabeças deslizantes implica comprometer-se com várias promessas:
- Todo o puzzle é solúvel.
- Todo o puzzle leva aproximadamente um dado número de movimentos (calibração de dificuldade).
- Todo o puzzle consegue produzir uma dica sob demanda.
Nenhuma destas promessas é honesta sem um solver a correr em segundo plano.
A geração solúvel-por-construção pode evitar correr um solver durante a geração: caminha-se para trás a partir do estado-objetivo aplicando movimentos válidos aleatórios, garantindo uma posição inicial solúvel. A maioria das apps, incluindo a nossa, faz exatamente isto.
A calibração de dificuldade quer que o puzzle seja "interessante" — nem trivial (um tabuleiro quase resolvido) nem extenuante (um tabuleiro que exige 60 movimentos para corrigir num 3×3). O truque padrão é aplicar passos para trás suficientes para ficar perto da distância ótima ao objetivo — tipicamente 20–30 para o 3×3, 40–60 para o 4×4. O solver verifica a distância após a geração.
As dicas exigem um solver capaz de produzir um bom próximo movimento em algumas centenas de milissegundos. É mais rápido do que uma solução ótima completa, mas continua a exigir trabalho algorítmico real.
Que tipo de solver
A escolha depende do tamanho do tabuleiro:
| Tabuleiro | Algoritmo recomendado | Tempo por resolução |
|---|---|---|
| 3×3 | A* + Manhattan | < 1 ms |
| 4×4 | IDA* + walking distance | 10 ms – 1 seg |
| 5×5 | IDA* + base de padrões 5+5+5+9 | 100 ms – minutos |
| 6×6 | IDA* + base de padrões maior | segundos – horas |
Para um 3×3, até o BFS por força bruta funciona. No 4×4 é preciso uma heurística a sério, e a distância de Manhattan é o padrão desde os anos 1980. No 5×5 são necessárias bases de padrões. No 6×6 está a fazer pesquisa.
Cobrimos os detalhes do algoritmo no guia do solver do 15-puzzle e no guia do solver do 8-puzzle. Para uma comparação de algoritmos, ver a página solver de quebra-cabeça deslizante.
No aparelho vs no servidor
As apps móveis que entregam um solver têm duas escolhas de implementação: corrê-lo no aparelho, ou chamar um servidor.
No aparelho é a escolha mais honesta para uma app que respeita a privacidade. O solver são algumas centenas de linhas de código, as bases de padrões para 4×4 cabem em alguns megabytes e um telemóvel moderno resolve qualquer 15-puzzle bem abaixo de um segundo. Não há razão para enviar um estado de puzzle para um servidor — e não o enviar é uma das coisas que distingue um jogo calmo de telemóvel de um que precisa de telemetria para funcionar.
No servidor é o que se usa quando o desenvolvedor quer registar em que puzzles os utilizadores ficam presos, ou fazer testes A/B a curvas de dificuldade. São razões reais de produto, mas vêm com um custo de privacidade e dependência de rede. Apps que não resolvem um puzzle offline são apps que não funcionam num avião.
O Slide Puzzle resolve totalmente no aparelho. A base de padrões do 4×4 tem cerca de 6 MB e vive dentro do bundle da app. O botão de dica usa-a diretamente. Nenhum pedido sai do telemóvel.
Uma nota pragmática
Se chegou aqui à procura de "um site de solver onde colo o meu tabuleiro e ele diz-me a resposta" — existem, e costumam ser solvers web do 8-puzzle. Servem para o 3×3. Para 4×4 e maiores, a experiência é desconfortável: digitar 16 números, ver uma sequência de 50 movimentos, tentar executar 50 movimentos específicos num tabuleiro físico. Ninguém gosta disso.
Os usos realistas de um solver de quebra-cabeça deslizante são:
- Verificar a sua própria implementação em código.
- Gerar um conjunto de tabuleiros de teste.
- Dentro de uma app, calcular uma dica.
Fora disso, aprender o método de linhas e colunas é mais rápido.