Em 1880, o criador de quebra-cabeças norte-americano Sam Loyd anunciou um prêmio de 1000 dólares para quem resolvesse um jogo do 15 específico: a disposição padrão de 1 a 15 com o 14 e o 15 trocados. A febre dos quebra-cabeças já tomava conta dos Estados Unidos e da Europa, e a jogada publicitária de Loyd jogou lenha na fogueira. Milhares tentaram. Ninguém ganhou.
Havia um motivo para ninguém ganhar. O tabuleiro de Loyd era comprovadamente insolúvel, e a demonstração é elementar o bastante para caber numa página. Este artigo é essa página.
A afirmação
Exatamente metade das 16! ≈ 20.922.789.888.000 maneiras de dispor quinze peças e um espaço vazio num tabuleiro 4×4 pode ser levada até o objetivo padrão. A outra metade não pode. O "14 e 15 trocados" de Loyd está na metade insolúvel.
Isso vale de forma geral. Em todo quebra-cabeça deslizante N×N, metade das disposições é insolúvel. O jogo do 8 3×3 tem 9!/2 = 181.440 tabuleiros solúveis num total de 362.880; o jogo do 24, o jogo do 35 e assim por diante seguem a mesma regra.
Inversões
A demonstração precisa de uma definição. Leia as peças em 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. Você 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 todos esses pares 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 com a contagem de inversões quando você faz um movimento legal?
-
Deslizes horizontais (uma peça se move 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. Sua ordem relativa em relação a todas as outras peças continua exatamente igual, porque o movimento horizontal não altera a linha em que a peça está nem as peças que vêm antes ou depois dela na ordem da linha. A contagem de inversões não muda.
-
Deslizes verticais (uma peça se move 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 da linha que ela atravessa ao sair ou entrar. Cada uma dessas três passa de "depois" para "antes" ou vice-versa, ou seja, 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.
Resumindo: um deslize horizontal preserva a paridade da contagem de inversões (par ou ímpar). Um deslize vertical inverte essa paridade.
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 leva o vazio uma linha para cima ou para baixo, então a paridade da linha do vazio muda (linha par ↔ linha ímpar).
Agora temos duas coisas que mudam juntas:
- A paridade da contagem de inversões se inverte ⇔ deslize vertical.
- A paridade da linha do vazio se inverte ⇔ deslize vertical.
A soma das duas é, portanto, invariante em qualquer deslize legal. Encontramos uma grandeza conservada.
O teorema da paridade
Defina o invariante:
P = (contagem de inversões) + (número da linha do vazio, contado a partir de baixo, começando em 1)
Esta é a grandeza conservada. Em cada deslize legal, P muda por um número par, então sua paridade (par ou ímpar) nunca muda.
O estado-objetivo tem zero inversões e o vazio na linha 1 contando de baixo, portanto P = 1 (ímpar). Qualquer tabuleiro com P par é inalcançável a partir do objetivo e, da mesma forma, o objetivo é inalcançável a partir desse tabuleiro.
Isso dá um teste de solubilidade claro para o jogo do 15:
- Leia as peças em ordem de linhas, ignorando o vazio.
- Conte as inversões.
- Conte a linha do vazio a partir de baixo (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 contando de baixo: soma 2, par, insolúvel.
Como isso funciona em 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 somente 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 somente se (contagem de inversões) + (linha do vazio a partir de baixo) for ímpar.
Num 3×3, o teste se resume a "há um número par de inversões?". É mais simples do que a versão 4×4, e você decora em um 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. Os aplicativos que precisam garantir posições iniciais solúveis fazem uma de duas coisas:
- Filtram com o teste de paridade e misturam de novo em caso de falha.
- Geram caminhando para trás a partir do objetivo, aplicando deslizes válidos aleatórios. Isso garante a solubilidade por construção e é o que a maioria dos aplicativos faz, incluindo o nosso.
Se algum dia você jogar um quebra-cabeça deslizante e achar que é impossível, seja lá o que você fizer, foi o aplicativo que gerou errado. A culpa não é sua, e não é nenhum mistério do universo.
A nota de rodapé sobre Sam Loyd
O prêmio de 1000 dólares de Loyd é uma das pegadinhas mais bem documentadas da história dos quebra-cabeças. 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 você acredita. Loyd era famoso pela autopromoção e reivindicou várias invenções que não eram dele; o próprio jogo do 15 foi inventado por Noyes Chapman em 1874, seis anos antes da jogada publicitária de Loyd.
O que Loyd de fato contribuiu foi o prêmio, a publicidade e a variante insolúvel. Uma contribuição útil, ainda que não fosse a que ele anunciava.