Existe um método para resolver à mão quebra-cabeças deslizantes. Não depende do tamanho do tabuleiro. Quando o domina no 3×3, domina-o no 4×4, no 5×5, no 6×6 e em qualquer tamanho maior que encontre. É este o método.
O plano
Para um puzzle N×N:
- Resolva a linha 1 — coloque as peças 1, 2, …, N na linha de cima.
- Resolva a coluna 1 — coloque as peças N+1, 2N+1, …, na primeira coluna abaixo da linha 1.
- Tem agora um puzzle (N−1)×(N−1). Recorra.
- Caso base — quando chegar a um 2×2, as peças restantes estão no sítio ou precisa de consultar uma verificação de paridade.
É todo o algoritmo. Três frases. O resto é mecânica.
A mecânica: cantos
Colocar as primeiras peças de uma linha ou de uma coluna é fácil. O truque está em colocar a última peça — a peça do canto.
Para o canto superior direito da linha 1 (peça N num puzzle N×N):
- Não tente deslizar a peça N diretamente para o canto. Não vai ficar lá.
- Coloque primeiro no canto a peça anterior (peça N−1).
- Coloque a peça N diretamente por baixo de N−1.
- Agora rode o par: mova o vazio para o canto (deslocando N−1), deslize N−1 para baixo-e-esquerda para sair do caminho, deslize N para cima para o canto, deslize N−1 para a direita.
O efeito é que N−1 e N ficam corretamente colocadas sem perturbar nada à sua esquerda.
Esta é a manobra em L do canto. O mesmo truque, espelhado, funciona no canto inferior esquerdo da coluna 1.
Se só conseguir lembrar-se de uma peça de técnica de quebra-cabeças deslizantes, lembre-se desta. Tudo o resto decorre dela.
A mecânica: meios
Para o interior de uma linha (peças 1 a N−2 na linha de cima), a colocação é direta:
- Encontre a peça que quer.
- Mova-a para uma posição adjacente ao seu destino.
- Use a célula vazia para a deslizar para o sítio.
Pode ter de empurrar outras peças não colocadas para o lado. Tudo bem — elas não estão colocadas. Desde que não mexa em peças já colocadas à esquerda, a linha forma-se de forma limpa.
A regra que o mantém em segurança: nunca deixe a célula vazia atravessar uma peça já colocada. Se o vazio precisa de viajar da direita do tabuleiro para a esquerda de uma peça colocada, tem de o levar à volta dela, passando por células não colocadas.
Por que "linha, depois coluna"
Duas razões:
- Simetria de espelho. A manobra do canto da linha e a manobra do canto da coluna são exatamente o mesmo truque, espelhado. Aprender uma ensina a outra.
- O vazio tem espaço para trabalhar. Depois de resolver a linha 1, o vazio tem as (N−1) linhas de baixo para se mexer. Depois de resolver a coluna 1, tem uma área (N−1)×(N−1). A área de trabalho encolhe graciosamente.
Podia alternar (linha 1, coluna 1, linha 2, coluna 2, ...) mas o ritmo natural é fazê-las em pares na periferia e recorrer.
A recursão
Quando a linha 1 e a coluna 1 estão feitas, o puzzle (N−1)×(N−1) restante contém peças que têm de ir para uma configuração-alvo diferente — a mesma sequência numérica, mas em posições diferentes. A boa notícia: o método não se importa. Resolva a nova linha de cima, a nova coluna da esquerda, recorra. Eventualmente bate num caso base 2×2 ou 3×3.
Para o caso base 3×3, as últimas três peças podem ser rodadas para o sítio com movimentos simples repetidos. Para um caso base 2×2 (que pode aparecer no final de puzzles grandes), aplica-se o mesmo.
Por que isto funciona em todos os tamanhos
A família dos quebra-cabeças deslizantes tem uma propriedade recursiva útil: resolver uma linha e uma coluna reduz o puzzle a um puzzle mais pequeno do mesmo tipo. A matemática é direta. Depois de colocar N peças na linha 1 (e nunca mais lhes tocar), o jogo restante vive numa grelha de largura (N−1) à qual falta uma linha. Depois de colocar a coluna mais à esquerda, vive numa grelha (N−1)×(N−1).
Pode aplicar esta redução a cada passo. O 6×6 reduz-se a 5×5, que reduz a 4×4, que reduz a um endgame 3×3. O endgame 3×3 é o único com uma técnica especial; tudo o que é maior reduz-se a ele.
Essa estrutura recursiva é por isso que os quebra-cabeças deslizantes são usados muitas vezes para ensinar divisão e conquista em disciplinas de programação. A prova de correção é um parágrafo; a implementação é o corpo do algoritmo.
A que velocidade chega
Um solver novo, a aplicar este método literalmente, leva:
Ao fim de alguns jogos por tamanho, esses tempos caem para metade. O método é o mesmo; é apenas memória motora da manobra do canto.
Para que este método não é bom
Soluções ótimas. Um computador com um solver a sério encontra sequências 30–50% mais curtas do que as que o método de linhas e colunas produz. Os humanos não conseguem correr esses algoritmos na cabeça.
Competições de speed-solving. Os melhores speed-solvers humanos usam o método de linhas e colunas como base, mas cortam atalhos de forma agressiva, fazendo colocações parciais que desfazem depois. É mais rápido, mas mais difícil de aprender.
Para toda a gente — o método de linhas e colunas é o método.