QUEBRA15

Regras desta versão

• Grade 4×4 com 15 peças e uma casa vazia. A meta é 1 a 15 em ordem de leitura, com o vazio no canto inferior direito.
• Só peças vizinhas do vazio se movem. Cada toque move uma única peça e conta 1: deslocar uma fileira de três peças custa três movimentos.
• Tocar numa peça que não é vizinha do vazio, ou no próprio vazio, não faz nada e não conta; o mesmo vale para uma seta sem peça para deslizar naquela direção.
• O embaralhamento parte do jogo resolvido e faz 220 movimentos aleatórios válidos, então toda partida tem solução garantida.
• Não há dica, desfazer nem cronômetro. "Nova Partida" sorteia outro embaralhamento a qualquer momento.
• O recorde aparece como "—" até a primeira vitória. O controle é por clique, toque ou teclado: as setas deslizam a peça na direção da seta, e Tab com Enter escolhem e movem uma peça vizinha do vazio, com o foco acompanhando a peça movida.

Por que toda partida tem solução

Existem 16! arranjos possíveis (cerca de 20,9 trilhões), mas só metade, 10,46 trilhões, pode ser alcançada deslizando; a outra metade é impossível, como demonstraram em 1879 W. W. Johnson e W. E. Story. Esta versão evita o problema embaralhando por movimentos legais, de modo que o tabuleiro nunca sai da metade alcançável.

A regra que separa as metades: conte as inversões (pares em que um número maior aparece antes de um menor na ordem de leitura, ignorando o vazio) e some a linha do vazio contando de baixo para cima, de 1 a 4. Se o total for ímpar, tem solução. No jogo resolvido, 0 + 1 = 1. Se você trocar só o 14 e o 15, dá 1 + 1 = 2: impossível, o célebre "14-15" de Sam Loyd.

Método por camadas, passo a passo

• 1. A linha de cima. Coloque o 1 e o 2 sem dificuldade. Para o 3 e o 4, não tente colocá-los em fila: leve o 4 para a casa do 3 e o 3 para logo abaixo dele, com o vazio no canto superior direito. Deslize o 4 para a direita e o 3 para cima: a linha fecha em dois movimentos.
• 2. A coluna da esquerda. Coloque o 5. Depois leve o 13 para a casa do 9 e o 9 para a direita dele, com o vazio embaixo do 13. Deslize o 13 para baixo e o 9 para a esquerda.
• 3. O quadrado 3×3 que sobrou. Repita o mesmo truque: primeiro a linha do 6, 7 e 8, depois a coluna do 10 e do 14.
• 4. Os três últimos. Sobram 11, 12 e 15 e o vazio num quadrado 2×2. Gire as três peças em volta do vazio até a ordem fechar: a regra de paridade garante que fecha.

O que o contador de movimentos esconde

Cada movimento leva o vazio a uma casa vizinha, então a paridade do total de movimentos é fixa para cada tabuleiro: é igual à paridade da distância, em passos, entre o vazio e o canto de chegada. Se o vazio começa no canto superior esquerdo, a 6 passos do destino, toda solução, curta ou longa, terá número par de movimentos. Por isso a menor melhora possível, no mesmo tabuleiro, é de 2 movimentos.

Há também um teto: nenhum tabuleiro exige mais de 80 movimentos de quem joga com perfeição, valor provado por computador em 2005. E um piso: o mínimo nunca é menor que a soma, peça a peça, das casas que faltam até o destino. Em simulações do mesmo embaralhamento deste jogo, essa soma fica perto de 28 em média, abaixo dos cerca de 37 de um sorteio uniforme entre os tabuleiros solúveis.

Estratégias

• Pense no vazio como a ferramenta. Em espaço aberto, mover uma peça uma casa custa 1 movimento se o vazio já está na frente dela e 5 se está atrás, porque precisa contorná-la. Transportar peças de longe é caro.
• Use a soma das distâncias como bússola. Some, para cada peça, quantas casas faltam até o destino. Um movimento que reduz a soma é progresso; um que aumenta só vale se for parte de um truque, como o do canto.
• Feche duas peças de uma vez. O truque do canto coloca o par 3 e 4 (ou 9 e 13) numa única manobra e evita o impasse de encaixar as duas em fila.
• Para um recorde baixo, avalie o tabuleiro antes de começar. Sorteios com soma de distâncias baixa são os mais fáceis. Como "Nova Partida" não custa nada, trocar um tabuleiro ruim é uma escolha sua.
• Antes de cada movimento, pergunte-se se vai desmanchar uma peça já pronta. Se sim, é preciso ter motivo.

Erros comuns

• Colocar o 1, 2, 3 e 4 em fila. O 4 só entra se o 3 sair do caminho; o truque do canto existe por isso.
• Mover ao acaso "para ver se resolve". São 10 trilhões de estados: sem plano, a chance de acertar é desprezível.
• Desfazer o próprio movimento. Mover uma peça e movê-la de volta gasta 2 movimentos sem mudar nada.
• Desmanchar a camada pronta. Mexer numa peça já resolvida costuma custar muitos movimentos para recompor.
• Achar que a partida é impossível. Não é: o que trava é a técnica, não o tabuleiro.

Dicas para iniciantes

• Nas primeiras partidas, ignore o contador e foque em aprender o método.
• Resolva a linha de cima, depois a coluna da esquerda, e repita o processo no quadrado menor que sobra.
• Se travar, volte uma etapa: é mais barato reorganizar a camada atual do que desistir.
• Repare em como o vazio se move: ele é o que realmente "anda" no tabuleiro.

Versão mobile

No celular, toque na peça vizinha ao espaço vazio para deslizá-la. O tabuleiro tem cerca de 350 px de largura, com peças de 76 px de lado, grandes o bastante para toques precisos. Não há arrastar: cada toque move uma peça e conta 1 movimento. As setas do teclado funcionam no computador; no celular, o controle é o toque.

História

O jogo é atribuído a Noyes Chapman, um agente de correio de Canastota, no estado de Nova York, que o teria apresentado a amigos por volta de 1874. Em 1880 virou febre nos Estados Unidos e na Europa. Sam Loyd, famoso criador de enigmas, afirmou ter inventado o jogo, o que pesquisadores depois desmentiram, e ficou associado ao desafio impossível do "14-15", que teria valido uma recompensa de US$ 1.000, segundo a história que ele próprio contava.

Curiosidades

• A versão menor, 3×3, tem 181.440 tabuleiros alcançáveis, contra 10,46 trilhões da 4×4.
• O Quebra-Cabeça 15 é um exemplo clássico em cursos de inteligência artificial para ensinar busca com heurística.
• O embaralhamento daqui é um passeio aleatório de 220 movimentos e pode voltar sobre os próprios passos: por isso a dificuldade varia de partida para partida.