Isto é um guia processual. Imprima-o, ou leia-o ao lado de um 15-puzzle acabado de baralhar no telemóvel, e siga os passos. No fim terá um método que resolve qualquer 15-puzzle em três a sete minutos.
O que se procura
O tabuleiro 4×4 com as peças por ordem:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 _
A célula vazia fica no canto inferior direito.
Passo 1 — resolver a linha de cima (1, 2, 3, 4)
Coloque a peça 1 primeiro no canto superior esquerdo. Isto é fácil — desloque peças até o 1 cair na posição. Não se preocupe em mexer no resto, porque nada está ainda no sítio.
Coloque a peça 2 à direita do 1. Mesma abordagem: traga o 2 para o topo e depois encoste-o ao 1.
Agora chega à parte tramada: as peças 3 e 4 têm de ir para a parte superior direita da linha, mas não basta colocar o 4 lá — quando o 4 ocupa o canto superior direito, normalmente precisa que o 3 entre a seguir, e fazer o 3 entrar costuma deslocar o 4.
A técnica:
- Coloque o 4 primeiro no canto superior direito.
- Coloque o 3 diretamente por baixo do 4 (na posição 8, célula direita da segunda linha).
- Agora rode o par 4-3 em sentido horário para o canto. Isto significa: mover a célula vazia para a direita do 4 (posição 4, o próprio canto superior direito), deslizar o 4 para a esquerda, deslizar o 3 para cima, deslizar o 4 para a direita.
Depois desta rotação, o 3 e o 4 ficam no sítio e o resto do tabuleiro apenas foi levemente perturbado. A linha de cima fica travada.
(Esta rotação é a manobra em L do canto. Decore-a — vai usá-la em cada canto de linha e em cada canto de coluna de cada puzzle pelo resto da vida.)
Passo 2 — resolver a coluna da esquerda (5, 9, 13)
Não mexa na linha de cima. A partir daqui só trabalha com as três linhas de baixo.
Coloque a peça 5 na posição 5 (topo da coluna da esquerda, logo abaixo do 1). É normalmente um ou dois deslizes.
Coloque a peça 9 abaixo do 5. Mesma abordagem.
Coloque as peças 13 e... espere, só lhe restam três peças da coluna da esquerda (5, 9, 13) — o canto inferior esquerdo é o 13. Use a mesma manobra em L do canto, espelhada verticalmente:
- Coloque o 13 na posição 9 (a célula onde o 9 estava — espere, o 9 já está lá).
- Na verdade, o movimento padrão: coloque o 9 primeiro no canto inferior esquerdo, coloque o 13 diretamente à sua direita e depois rode o par em sentido horário para a posição: vazio acima do 9, deslize o 9 para cima, deslize o 13 para a esquerda, deslize o 9 para baixo.
Depois disto, a linha de cima e a coluna da esquerda ficam travadas. Está a trabalhar num subpuzzle 3×3.
Passo 3 — resolver o endgame 3×3
O que sobra é uma grelha 3×3 (linhas 2-3-4, colunas 2-3-4) com as peças 6, 7, 8, 10, 11, 12, 14, 15 e o vazio. As posições-alvo dentro desta sub-grelha são:
6 7 8
10 11 12
14 15 _
Agora é um 8-puzzle com um estado-objetivo diferente, mas as mesmas regras. Aplique recursivamente o mesmo método de linhas e colunas:
- Resolva a parte de cima da sub-grelha (peças 6, 7, 8). Coloque o 6 primeiro. Depois, o canto 7-8 usa de novo a rotação em L.
- O 2×2 de baixo contém 10, 11, 14 e 15. Três peças e o vazio. Normalmente, consegue rodá-las para a posição com movimentos simples repetidos.
Se o 2×2 de baixo acabar com duas peças trocadas, isso significa que o puzzle original é insolúvel — o que só acontece se a app o gerou mal, e não por acaso a partir de uma mistura aleatória seguida de verificação de paridade.
Pontos comuns onde se fica preso
"Tenho tudo, mas as peças 3 e 4 estão invertidas." É o truque da rotação do canto. Tire ambas do canto em conjunto e depois rode-as de volta com a orientação correta.
"Estou a tentar colocar uma peça mas cada movimento estraga o que já tinha colocado." Está dentro de uma linha ou coluna que já travou. Recue um passo e verifique que peças "devem ficar quietas" — depois de uma linha ou coluna ficar travada, só pode trabalhar na zona desbloqueada abaixo ou à direita.
"O meu puzzle não acaba — as últimas duas peças estão trocadas." Dois casos: ou mexeu por engano numa peça travada (raro), ou o puzzle é insolúvel (também raro). Verifique reiniciando e usando o teste de paridade.
Quão rápido pode ficar
Um solver de primeira viagem, a aplicar literalmente este método, leva 15-25 minutos. À terceira resolução, o mesmo método leva 8 minutos. À décima, 3-5 minutos. Os speed-solvers abaixo dos dois minutos usam o mesmo método com memória motora.
Não existe um método humano mais rápido. A redução por linhas e colunas é, comprovadamente, a técnica manual mais limpa conhecida. As soluções ótimas por computador são mais curtas (~52 movimentos num tabuleiro aleatório), mas exigem algoritmos de busca; um humano a implementá-las precisaria de planear mais de vinte movimentos à frente, o que é impraticável.
O que vem a seguir
Quando o 4×4 se tornar rotina, o mesmo método funciona no 24-puzzle (5×5) e no 35-puzzle (6×6) sem alterações — apenas mais linhas e colunas para descascar antes de chegar ao 3×3 embebido.
Se quer o método geral sem os pormenores do 4×4, veja como resolver um quebra-cabeça deslizante. Se quer o exemplo trabalhado mais simples possível, veja solução do quebra-cabeça deslizante 3×3.