Em 1890, o designer de jogos e puzzles Sam Loyd ofereceu 1000 dólares para quem resolvesse o “Desafio 14-15” abaixo.

Consiste num tabuleiro 4×4 com um vazio, e as peças deslizam para o espaço vazio.

Note que as posições 14 e 15 estão invertidas, e o objetivo é arrumar o tabuleiro todo em ordem crescente.

O desafio e a facilidade de mexer no joguinho tornaram o mesmo uma febre, à época. Porém, desde então, o problema nunca obteve uma solução válida, por um motivo muito simples: é impossível.

Muita gente já deve ter brincado com esse quando criança, mas com a versão solúvel do mesmo (ou seja, o 14 e 15 na posição correta). Vou chamar a versão solúvel de “Puzzle do 15”, ao invés de “Desafio 14-15”.

Segue uma versão Excel do “Puzzle do 15”.

Um duplo clique na célula vai mover a peça para o posição vazia adjacente.

As macros devem estar ativadas para funcionar.

Link para download: https://1drv.ms/x/s!Aumr1P3FaK7jn2Lesl-PB1Z-O3Yi.

Também deixei a planilha no Github: asgunzi/Puzzle-do-15-Excel: Versão Excel do Puzzle do 15 (github.com)

Sobre a insolubidade do “Desafio 14-15”

A prova tradicional consiste em encontrar uma propriedade invariante, e mostrar que o 14 e 15 trocados não respeitam a propriedade.

A invariante, no caso, é a paridade do número de permutações. Porém, eu fiquei o dia inteiro pensando numa prova mais intuitiva e menos formal, que vou explorar a seguir.

Imagine não que as peças se movem, mas que o vazio se move.

Para que o espaço vazio comece e termine no canto inferior direito, ele tem que fazer um circuito fechado. Pintando de outra cor as células que sofreram alteração. Lembre-se de que a seta indica o espaço vazio que se move, então a peça cheia move-se no sentido contrário da seta.

Note que a peça vazia teve que ir para a esquerda e depois voltar para a direita, subir e depois descer.

Todas as vezes que a peça vazia subir, uma hora vai ter que descer; todas as vezes que for para a esquerda, uma hora deve voltar à direita, para que termine no canto inferior direito.

Outro tour possível:

O vazio andou dois para esquerda, dois para a direita, um para cima e um para baixo.

Um tour um pouco mais complicado, mas é a mesma lógica.

Agora, olhe para o “Desafio 14-15”:

Imagine começar da configuração possível e tentar chegar nessa configuração 15-14.

É uma posição esquisita, porque se o vazio percorrer somente a última linha, ele tem que ir à esquerda e voltar à direita, e nada vai mudar de lugar.

Se o vazio subir e descer, teria que bagunçar alguma coisa na linha de cima.

Se bagunçar e tentar consertar a linha de cima, automaticamente conserta a de baixo também, nunca chegando à posição 15-14.

É uma prova informal, só para dar uma intuição.

A prova mais formal diz que a paridade da permutação, mais a “distância de táxi” do vazio tem que ser par, porque quando muda uma coisa, a outra muda também.

O mais importante: Divirta-se com o “Puzzle do 15”!

Veja também:

15 puzzle – Wikipedia

Parity of a permutation – Wikipedia

Lab. Matemática