"Quebra-cabeça deslizante" é o nome-guarda-chuva. Debaixo dele estão meia dúzia de puzzles com nome próprio, todos partilhando uma regra — uma peça só se pode mover para uma célula vazia adjacente — e variando tudo o resto: forma do tabuleiro, número de peças, número de células vazias, se as peças podem rodar. Este guia percorre a árvore genealógica.
O ramo da grelha quadrada: N-puzzles
A linha principal da família. Um tabuleiro quadrado com N² − 1 peças numeradas (ou com imagem) e uma célula vazia.
| Nome | Tabuleiro | Peças | Resolução ótima mais difícil |
|---|---|---|---|
| 8-puzzle | 3×3 | 8 | 31 movimentos |
| 15-puzzle | 4×4 | 15 | 80 movimentos |
| 24-puzzle | 5×5 | 24 | 152 movimentos |
| 35-puzzle | 6×6 | 35 | est. 245 movimentos |
| 48-puzzle | 7×7 | 48 | desconhecido (pesquisa) |
| 80-puzzle | 9×9 | 80 | desconhecido |
A mesma estratégia — resolver a linha de cima, resolver a coluna da esquerda, recorrer — funciona em todos os tamanhos desta coluna. Tabuleiros maiores significam tempos de resolução maiores, não puzzles diferentes.
São os puzzles a que a maioria se refere quando diz "quebra-cabeça deslizante". São também aqueles em que os cientistas de computação fazem benchmark.
Grelhas não quadradas
Menos comuns, mas interessantes:
Retangulares — tabuleiros 3×4, 4×5, 5×6. Algumas versões comerciais, incluindo as de madeira do século XIX, eram retangulares. A mesma estratégia funciona; a manobra em L do canto é ligeiramente diferente na aresta assimétrica.
Hexagonais — peças numa grelha hexagonal, seis vizinhos possíveis por célula em vez de quatro. Matematicamente mais permissivas (mais opções de movimento por estado), psicologicamente mais confusas. Um nicho.
Triangulares — peças numa grelha triangular. Ainda mais raras. A matemática está bem; o jogo é desajeitado.
Mais do que uma célula vazia
A versão de uma única célula vazia é o padrão. Existem puzzles comerciais com duas ou mais células vazias — o mais famoso é o Klotski e os seus parentes, em que peças de tamanhos diferentes (1×1, 1×2, 2×2) deslizam num tabuleiro com algumas células vazias. O Klotski é, estrategicamente, um jogo diferente: não se está a tentar pôr as peças por ordem, mas a manobrar uma peça específica até uma saída.
O Klotski é por vezes agrupado em "quebra-cabeça deslizante". Não é mesmo parte da família — objetivo diferente, estratégia diferente, estrutura matemática diferente.
Deslizar mais rotação
Combine a regra do deslize com uma mecânica de rotação e obtém uma grande variedade de puzzles físicos: os Hungarian Rings, certos produtos próximos do Cubo de Rubik, e os chamados puzzles "loopover". Cruzam-se com a família dos quebra-cabeças deslizantes, mas, mais uma vez, são estrategicamente diferentes.
Para um jogador que vem do 15-puzzle, o primo mais próximo é o Rubik's 15 — um pequeno brinquedo físico com o layout do 15-puzzle, mas com a restrição de que pares adjacentes também podem ser trocados.
O que une a família
Dois factos matemáticos tornam a família dos quebra-cabeças deslizantes coerente:
-
Estrutura de grafo de estados. Cada variante pode ser modelada como um grafo: os nós são estados do tabuleiro, as arestas são movimentos legais. A resolução ótima é o caminho mais curto neste grafo. O grafo é enorme mas bem-comportado, e é por isso que a busca heurística funciona tão bem.
-
Invariantes de paridade. A maioria das variantes — incluindo todos os N-puzzles padrão — tem uma regra de paridade que divide os estados alcançáveis em duas metades. Metade são alcançáveis a partir do objetivo; metade não. As apps que geram posições iniciais aleatórias ou filtram à partida com o teste de paridade, ou geram caminhando para trás a partir do objetivo.
O que jogar, conforme o humor
Se nunca experimentou nenhum:
- Comece com o 8-puzzle durante dez minutos. É rápido o suficiente para absorver a regra e tentar a estratégia.
- Passe ao 15-puzzle quando o 8 parecer trivial. Esta é a experiência canónica.
- Experimente o 24-puzzle quando quiser um momento mais longo, sentado.
- Experimente o Klotski se quiser um quebra-cabeça deslizante diferente — mesma mecânica, objetivo diferente.
- Experimente grelhas hexagonais se quiser sentir-se principiante outra vez. Vão humilhá-lo.
A maioria das apps modernas, a nossa incluída, traz os 8-, 15-, 24- e 35-puzzles num só pacote. É o tronco central da família, e é no tronco central que quase toda a gente joga.