O 15-puzzle — por vezes "puzzle dos quinze", "Mystic Square" ou simplesmente "o deslizante 4×4" — é o quebra-cabeça deslizante canónico. Um tabuleiro 4×4 com quinze peças quadradas numeradas e uma célula vazia. Faz-se deslizar as peças para a célula vazia, um movimento de cada vez, até os números ficarem em ordem: 1‑2‑3‑4 no topo, 5‑6‑7‑8, 9‑10‑11‑12, 13‑14‑15 e o vazio no canto inferior direito.
De onde veio
O puzzle foi inventado em 1874 por um chefe-de-correio de Canastota, Nova Iorque, chamado Noyes Palmer Chapman. Em 1880 já tinha chegado às escolas de Boston; em meados de 1880 era febre nos Estados Unidos; e no outono já tinha atravessado o Atlântico e tomado conta da Grã-Bretanha, França e Alemanha. Os jornais publicavam colunas de soluções. Operários abandonavam o trabalho para resolver puzzles. As autoridades de algumas cidades alemãs terão chegado a proibi-lo em espaços públicos porque os funcionários não faziam outra coisa.
Sam Loyd — o criador de puzzles de Nova Iorque, nunca falto de uma boa história de autopromoção — afirmou tê-lo inventado, o que não era verdade, e ofereceu 1000 dólares em dinheiro a quem resolvesse uma variante específica com o 14 e o 15 trocados. Acontece que essa variante era matematicamente insolúvel (ver paridade do 15-puzzle para a demonstração). Ninguém ganhou. Loyd ficou feliz.
Como se joga
Três regras:
- Só pode deslizar uma peça que esteja adjacente à célula vazia — diretamente acima, abaixo, à esquerda ou à direita. Sem diagonais.
- O deslize move a peça para a célula vazia. A célula vazia passa para onde a peça estava.
- Terminou quando as peças estão por ordem numérica.
É isso. Não há limite de tempo, não há pontuação, não há um segundo objetivo. O jogo inteiro cabe nestas três frases.
Quão difícil é?
O 15-puzzle tem 16!/2 ≈ 10,46 biliões de disposições alcançáveis (metade do total de 16!, por causa da regra de paridade). A solução mais curta a partir da posição inicial mais difícil é de 80 movimentos. A mediana ronda os 52.
Um jogador novo resolve o seu primeiro 15-puzzle em 15–30 minutos por tentativa e erro. Um jogador que aprendeu o método de linhas e colunas no 8-puzzle resolve qualquer 15-puzzle em 3–7 minutos. Um speed-solver, com movimentos otimamente escolhidos, fá-lo em menos de 90 segundos.
O que torna o 4×4 o ponto ideal
Há uma razão para o 15-puzzle, e não o 8 ou o 24, ter sido o fenómeno mundial. O tabuleiro 4×4 é:
- Longo o suficiente para ser satisfatório. O 8-puzzle resolve-se tão depressa que não tem arco. O 15 demora o suficiente para dar o pequeno alívio de um tabuleiro terminado.
- Curto o suficiente para não arrastar. O 24-puzzle leva mais de 15 minutos a um solver confiante. O 35-puzzle leva mais de 30. O 4×4 cabe dentro de uma pausa para café.
- Difícil o suficiente para pensar. A estratégia não é óbvia ao primeiro contacto. A "manobra em L do canto" tem de ser descoberta ou ensinada — e, uma vez aprendida, o puzzle inteiro se abre.
Esse ponto ideal é a razão pela qual o 15-puzzle é o tamanho que se usa como sinónimo de toda a família. As pessoas dizem "quebra-cabeça deslizante" e imaginam um 4×4.
Em ciência da computação
Durante décadas, o 15-puzzle foi o benchmark-padrão para algoritmos de busca heurística. O artigo de Richard Korf de 1985 que introduziu o IDA* usou 100 15-puzzles aleatórios para demonstrar a aceleração face ao A*. Os artigos modernos sobre bases de padrões continuam a reportar resultados no 15. O puzzle é pequeno o suficiente para ser tratável, e grande o suficiente para que algoritmos maus expirem.
Se alguma vez fez uma cadeira de "Introdução à IA", resolveu um 15-puzzle como exercício de programação. Provavelmente com A* e a heurística da distância de Manhattan. (Para material mais profundo, consulte o guia do solver.)
Variantes em apps modernas
O 15-puzzle tem algumas variantes modernas comuns:
- Peças numéricas — o original, simples algarismos nas peças.
- Peças de imagem — uma fotografia cortada em N×N substitui os números. Resolve-se reagrupando a imagem.
- Híbrido — peças de imagem com pequenos números opcionais sobrepostos, para quem quer uma pista sobre o sítio de cada peça.
Algumas apps vão mais longe: grelhas hexagonais, tabuleiros maiores (5×5 = 24-puzzle, 6×6 = 35-puzzle), puzzles de rotação em que as peças podem rodar, e assim por diante. A versão numérica 4×4 é a língua franca.
Onde jogar
No telemóvel, as apps nativas oferecem a experiência mais suave — sem upload, sem analítica, sem anúncios a interromper a meio de um deslize. O Slide Puzzle traz a versão numérica clássica mais 300 capas fotográficas e quatro tamanhos (3×3, 4×4, 5×5, 6×6).
Na web, há 15-puzzles em navegador às dezenas. São convenientes mas geralmente fazem upload das fotos importadas e correm analítica. Se quer só uns jogos e nunca importar uma foto sua, servem.
Se nunca resolveu um, comece pelo 8-puzzle durante trinta segundos — só para apanhar o movimento — e depois volte ao 15. A estratégia que se apanha no tabuleiro mais pequeno escala diretamente.