Se alguma vez passou trinta minutos num 15-puzzle que simplesmente não acaba — cada movimento que faz acaba por levar a duas peças trocadas no fim — há a possibilidade de o puzzle ser matematicamente insolúvel. Exatamente metade das disposições do 15-puzzle são-no. Uma app mal escrita pode gerar uma destas por acidente.
Este artigo é a verificação prática. A justificação matemática completa vive em o teorema da paridade; esta mantém-se simples.
A verificação em 30 segundos
Olhe para as peças por ordem de leitura — da esquerda para a direita em cada linha, de cima para baixo — ignorando o vazio.
Para cada par de peças, conte quantas vezes um número maior aparece antes de um menor. Esse total é o número de inversões.
A seguir, repare em que linha está a célula vazia, contando a partir do fundo (a linha de baixo é 1, a linha acima é 2, depois 3, depois 4 em cima).
Some o número de inversões e a linha do vazio a partir do fundo. Se o resultado for ímpar, o puzzle é solúvel. Se for par, não é.
É só isto. É toda a verificação.
Um exemplo trabalhado
Imagine que o seu tabuleiro tem este aspeto:
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 _
Ordem de leitura: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14.
Conte inversões. É preciso encontrar cada par em que um número maior aparece antes de um menor. Percorrendo: 15 aparece antes de 14, e essa é a única inversão. Logo, contagem de inversões = 1.
O vazio está na linha de baixo → linha 1 a partir do fundo.
Soma: 1 + 1 = 2. Par. Este tabuleiro é insolúvel.
É, de facto, o puzzle do prémio de Sam Loyd, de 1880. O homem ofereceu 1000 dólares a quem o resolvesse. O puzzle era insolúvel; ele guardou o dinheiro.
Outro exemplo
Imagine que o seu tabuleiro tem este aspeto:
5 1 3 4
2 6 7 8
9 10 11 12
13 14 15 _
Ordem de leitura: 5, 1, 3, 4, 2, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
Conte inversões:
- 5 antes de 1 → 1 inversão (5 > 1, e o 5 aparece primeiro)
- 5 antes de 3 → 1 inversão
- 5 antes de 4 → 1 inversão
- 5 antes de 2 → 1 inversão
- 3 antes de 2 → 1 inversão
- 4 antes de 2 → 1 inversão
Total de inversões: 6.
O vazio está na linha de baixo → linha 1.
Soma: 6 + 1 = 7. Ímpar. Este tabuleiro é solúvel.
Note que 6 + 1 = 7 é ímpar porque 6 é par e somamos um número ímpar — não, espere. 6 + 1 = 7, que é ímpar. Solúvel.
Por que funciona (em breve)
Um deslize legal ou move uma peça horizontalmente (sem mudança no número de inversões, sem mudança na linha do vazio) ou verticalmente (muda o número de inversões por um número ímpar, muda a linha do vazio por 1).
Em qualquer caso, a soma de inversões + linha do vazio mantém-se par-ou-ímpar do mesmo modo com que começou. Esta soma é, portanto, um invariante — uma propriedade do puzzle que os movimentos legais não conseguem alterar.
O estado-objetivo (1‑2‑3‑...‑15 com o vazio no canto inferior direito) tem 0 inversões e o vazio na linha 1 a partir do fundo. Soma: 1, ímpar. Logo, qualquer puzzle solúvel tem soma ímpar. Qualquer puzzle com soma par não consegue chegar ao objetivo.
Para a demonstração completa com todos os casos detalhados, ver a página do teorema da paridade.
E nos 8-puzzles (3×3)?
A verificação é mais simples para o 3×3:
- Conte inversões por ordem de leitura.
- Se for par, solúvel.
- Se for ímpar, insolúvel.
Não precisa de seguir a linha do vazio no 3×3, porque a simetria do puzzle torna a dependência da linha redundante.
(Para 5×5 — mesma regra do 3×3. Para 6×6 — mesma regra do 4×4. A regra é "a linha do vazio importa quando N é par".)
O que fazer se a sua app gerar puzzles insolúveis
Isto nunca devia acontecer. Uma app bem escrita usa um de dois métodos para o evitar:
Gerar caminhando para trás a partir do objetivo. Comece com o estado-objetivo, aplique movimentos válidos aleatórios e use o estado resultante como posição inicial. Toda a posição gerada assim é solúvel por construção.
Gerar aleatoriamente e testar a paridade. Baralhe as peças uniformemente ao acaso; calcule a verificação de paridade; se for par, troque duas peças quaisquer para a corrigir. A posição resultante fica garantidamente solúvel.
Se encontrar um puzzle insolúvel numa app, essa app está partida. Reporte o bug, mude de app. O Slide Puzzle usa o método de caminhar para trás a partir do objetivo e não consegue produzir posições iniciais insolúveis.
O que fazer se suspeitar que o seu próprio puzzle físico é insolúvel
Duas coisas:
- Faça a verificação. Inversões mais linha do vazio. Se for par, as peças físicas foram montadas incorretamente. Retire uma peça, troque-a com uma adjacente, e o puzzle fica solúvel.
- Se mesmo depois da troca o puzzle continuar a resistir-lhe — a resistência é a sua estratégia, não o puzzle.
A verificação de paridade leva cerca de trinta segundos. Fazê-la antes de gastar mais uma hora num tabuleiro preso é um uso razoável desses segundos.