Em 1880, o criador de puzzles norte-americano Sam Loyd anunciou um prémio de 1000 dólares para quem resolvesse um 15-puzzle específico: a disposição-padrão de 1 a 15 com o 14 e o 15 trocados. A febre dos puzzles já tomava conta da América e da Europa; o golpe publicitário de Loyd deitou combustível na fogueira. Milhares tentaram. Ninguém ganhou.
Houve uma razão para ninguém ganhar. O tabuleiro de Loyd era comprovadamente insolúvel, e a demonstração é elementar o suficiente para caber numa página. Este artigo é essa página.
A afirmação
Exatamente metade das 16!/2 ≈ 10 461 394 944 000 maneiras de dispor quinze peças e um espaço vazio num tabuleiro 4×4 pode ser resolvida até ao objetivo-padrão. A outra metade não pode. O "14 e 15 trocados" de Loyd está na metade insolúvel.
Isto generaliza-se. Em todos os quebra-cabeças deslizantes N×N, metade das disposições é insolúvel. O 8-puzzle 3×3 tem 9!/2 = 181 440 tabuleiros solúveis num total de 362 880; o 24-puzzle, o 35-puzzle, e por aí fora seguem a mesma regra.
Inversões
A demonstração precisa de uma definição. Leia as peças por ordem de leitura — da esquerda para a direita na linha 1, depois a linha 2, depois a 3, depois a 4 — e ignore o espaço vazio. Obtém uma sequência de quinze números.
Uma inversão é um par (a, b) em que a aparece antes de b na sequência, mas a > b. Conte cada par destes na sequência inteira. Esse total é o número de inversões do tabuleiro.
Exemplo: o estado-objetivo 1, 2, 3, …, 15 tem zero inversões. O "14 e 15 trocados" de Loyd tem a sequência 1, 2, 3, …, 13, 15, 14, com exatamente uma inversão (o par 15, 14).
O lema-chave: um deslize altera a paridade de forma controlada
O que acontece à contagem de inversões quando se faz um movimento legal?
-
Deslizes horizontais (uma peça move-se uma célula para a esquerda ou para a direita): a peça movida muda de posição em uma casa na sequência de leitura. A sua ordem relativa face a todas as outras peças mantém-se exatamente igual — porque o movimento horizontal não altera a linha em que a peça está nem as peças que a precedem ou seguem na ordem da linha. A contagem de inversões não muda.
-
Deslizes verticais (uma peça move-se uma célula para cima ou para baixo): a peça movida salta por cima de três outras peças na sequência de leitura — as três peças da linha que ela atravessa ao sair ou entrar. Cada uma dessas três passa de "depois" para "antes" ou vice-versa, o que significa que cada uma contribui com +1 ou −1 para a contagem de inversões. A soma de três ±1 é sempre ímpar. Logo, a contagem de inversões muda por um número ímpar.
Em resumo: um deslize horizontal preserva a paridade da contagem de inversões (par ou ímpar). Um deslize vertical inverte-a.
A linha do espaço vazio também muda nos deslizes verticais
Acompanhe a linha do espaço vazio, contando as linhas a partir do topo. Um deslize horizontal mantém o vazio na mesma linha. Um deslize vertical desloca-o uma linha para cima ou para baixo, pelo que a paridade da linha do vazio muda (linha par ↔ linha ímpar).
Temos agora duas coisas que mudam juntas:
- Paridade da contagem de inversões inverte ⇔ deslize vertical.
- Paridade da linha do vazio inverte ⇔ deslize vertical.
A sua soma é portanto invariante em qualquer deslize legal. Encontrámos uma grandeza conservada.
O teorema da paridade
Defina o invariante:
P = (contagem de inversões) + (número da linha do vazio, contado a partir do fundo, começando em 1)
Esta é a grandeza conservada. Em cada deslize legal, P muda por um número par, pelo que a sua paridade (par ou ímpar) nunca muda.
O estado-objetivo tem zero inversões e o vazio na linha 1 a contar do fundo — portanto P = 1 (ímpar). Qualquer tabuleiro com P par é inalcançável a partir do objetivo, e reciprocamente o objetivo é inalcançável a partir desse tabuleiro.
Isto dá um teste de solubilidade claro para o 15-puzzle:
- Leia as peças por ordem de linhas, ignorando o vazio.
- Conte as inversões.
- Conte a linha do vazio a partir do fundo (1, 2, 3 ou 4).
- Some. Se a soma for ímpar, o tabuleiro é solúvel. Se for par, não é.
O "14 e 15 trocados" de Loyd tem 1 inversão e o vazio na linha 1 a partir do fundo — soma 2, par, insolúvel.
Como isto se traduz para outros tamanhos
A regra de paridade N×N depende de N ser par ou ímpar. O enunciado geral:
- N ímpar (3×3, 5×5, …): um tabuleiro é solúvel se e só se a contagem de inversões for par. A linha do vazio não importa, porque a paridade da linha do vazio é determinada pela paridade da contagem de inversões por razões de simetria.
- N par (4×4, 6×6, …): um tabuleiro é solúvel se e só se (contagem de inversões) + (linha do vazio a partir do fundo) for ímpar.
Para um 3×3, o teste resume-se a "há um número par de inversões?". É mais simples do que a versão 4×4, e memoriza-se num minuto.
Uma consequência interessante
Como exatamente metade das disposições é solúvel, uma mistura aleatória seguida do teste de paridade é mais rápida do que uma mistura aleatória seguida de tentar resolver. As apps que precisam de garantir posições iniciais solúveis fazem uma de duas coisas:
- Filtram com o teste de paridade e voltam a misturar em caso de falha.
- Geram caminhando para trás a partir do objetivo, aplicando deslizes válidos aleatórios. Isto garante solubilidade por construção e é o que a maioria das apps faz, incluindo a nossa.
Se algum dia jogar um quebra-cabeça deslizante e o achar impossível, faça o que fizer, foi a app que o gerou mal — não é culpa sua, e não é um puzzle do universo.
A nota de rodapé sobre Sam Loyd
O prémio de 1000 dólares de Loyd é uma das partidas mais bem documentadas da história dos puzzles. O matemático que provou a insolubilidade — de forma independente — foi William Johnson e William Story (1879, American Journal of Mathematics) ou o próprio Loyd, dependendo da versão em que se acredita. Loyd era uma figura famosa pela autopromoção e que reivindicou várias invenções que não fez; o próprio 15-puzzle foi inventado por Noyes Chapman em 1874, seis anos antes do golpe publicitário de Loyd.
O que Loyd verdadeiramente contribuiu foi o prémio, a publicidade e a variante insolúvel — um contributo útil, ainda que não o que ele anunciava.