Uma breve história dos quebra-cabeças de blocos deslizantes

A ideia central é um quadro com peças e espaço insuficiente: uma peça desliza para o espaço vazio. Ela já aparecia em papel antes da versão mais famosa. Uma patente americana concedida a Ernest Kinsey em 1878 descreveu blocos que deslizam em um quadro com um único espaço vazio.

O jogo que popularizou o formato foi o quebra-cabeça de 15 peças: quinze peças numeradas em um tabuleiro quatro por quatro, com um espaço vazio. Pesquisas históricas de Jerry Slocum e Dic Sonneveld, reunidas no livro The 15 Puzzle, de 2006, remontam a Noyes Chapman, chefe dos correios de Canastota, no estado de Nova York. Versões eram vendidas como Gem Puzzle no fim de 1879.

Fontes1Fonte 1Kinsey, E. U. (1878). Improvement in puzzle-blocks (U.S. Patent No. 207,124). U.S. Patent Office.2Fonte 2Slocum, J., & Sonneveld, D. (2006). The 15 puzzle: How it drove the world crazy. Slocum Puzzle Foundation.

Nos primeiros meses de 1880, o jogo virou febre. Em poucas semanas, espalhou-se pelos Estados Unidos e depois pela Europa, chegando a escritórios, salas de estar e jornais. Os relatos divergem sobre as datas exatas; na primavera já era onipresente e no verão perdeu força. Chapman pediu uma patente, que foi negada; a razão não é certa, mas patentes anteriores talvez já cobrissem a ideia.

Algumas posições pareciam impossíveis — e eram mesmo. Em 1879, William Woolsey Johnson e William Story publicaram no American Journal of Mathematics uma demonstração de que exatamente metade das posições não tem solução. Cada deslize preserva uma propriedade de paridade; se a posição inicial tiver a paridade errada, ela nunca será alcançada.

Isso explica o exemplo mais famoso: troque apenas as peças 14 e 15 de um tabuleiro resolvido. Parece faltar um único movimento para terminar, mas a posição é inalcançável.

Fontes3Fonte 3Johnson, W. W., & Story, W. E. (1879). Notes on the “15” puzzle. American Journal of Mathematics, 2(4), 397–404.

Durante boa parte do século XX, o quebra-cabeça de 15 peças foi atribuído a Sam Loyd, famoso autor de desafios nos Estados Unidos. Ele dizia tê-lo inventado e oferecia um prêmio para quem resolvesse a troca impossível entre 14 e 15. Slocum e Sonneveld descobriram que a primeira alegação apareceu em 1891, mais de dez anos depois da febre, e persistiu até a morte de Loyd, em 1911. Não há evidências de que ele tenha inventado o jogo ou de que o prêmio tenha existido em 1880.

A história persistiu por causa da fama de Loyd, da reimpressão de seus livros e de relatos posteriores. Como qualquer história, a dos quebra-cabeças também precisa ser conferida nos documentos.

Fontes2Fonte 2Slocum, J., & Sonneveld, D. (2006). The 15 puzzle: How it drove the world crazy. Slocum Puzzle Foundation.

A geração seguinte mudou o objetivo. Em vez de ordenar peças, era preciso levar um bloco grande até uma saída entre blocos menores. Uma patente solicitada por Lewis W. Hardy em 1907 e concedida em 1912 descreve dez blocos de vários tamanhos dentro de uma caixa, movidos apenas por deslizes. Um modelo semelhante foi vendido como Pennant Puzzle.

Vieram jogos parecidos com vários nomes. O Smithsonian conserva o Dad’s Puzzler, patenteado em 1926, com um quadrado grande, retângulos e dois quadrados pequenos. Essa família é conhecida como Klotski; na China, Huarong Dao conta a história de um general escapando de uma emboscada. Dependendo da forma de contar, soluções mínimas clássicas chegam a cerca de 80 movimentos.

Na década de 1990 surgiu uma versão moderna de grande sucesso. Nob Yoshigahara, do Japão, criou Tokyo Parking, um quebra-cabeça de carros deslizantes; a Binary Arts, mais tarde ThinkFun, lançou-o nos Estados Unidos como Rush Hour, em 1996. Carros e caminhões ocupam uma grade pequena e precisam ser movidos para liberar o carro do jogador. Cartas com dificuldade gradual fizeram do jogo uma presença comum em escolas e famílias.

Fontes4Fonte 4Hardy, L. W. (1912). Puzzle (U.S. Patent No. 1,017,752). U.S. Patent Office.5Fonte 5Smithsonian National Museum of American History. (n.d.). Dad’s Puzzler, once owned by Olive C. Hazlett [Object 2015.0027.04].6Fonte 6Contreras, M. (2018, February 1). The evolution of ThinkFun’s Rush Hour. ThinkFun. Archived by the Internet Archive, 25 December 2022.

Parecem brinquedos, mas são objetos sérios da ciência da computação. Só em 1999 se estabeleceu que qualquer posição solucionável do quebra-cabeça de 15 peças pode ser resolvida em no máximo 80 movimentos de uma peça. Korf e Schultze confirmaram o resultado com uma busca de 28 dias que encontrou exatamente dezessete posições que exigiam os 80 movimentos.

Em 2002, Gary Flake e Eric Baum provaram que Rush Hour generalizado para tabuleiros de qualquer tamanho é PSPACE-completo, uma classe considerada mais difícil que os conhecidos problemas NP-completos. Robert Hearn e Erik Demaine mostraram em 2005 que quebra-cabeças gerais de blocos deslizantes também são PSPACE-completos, mesmo usando apenas dominós pequenos e iguais. Não há atalho conhecido para resolver rapidamente todos os tabuleiros — por isso um bom quebra-cabeça continua interessante.

Fontes7Fonte 7Korf, R. E., & Schultze, P. (2005). Large-scale parallel breadth-first search. In Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI-05) (pp. 1380–1385). AAAI Press.8Fonte 8Flake, G. W., & Baum, E. B. (2002). Rush Hour is PSPACE-complete, or “Why you should generously tip parking lot attendants”. Theoretical Computer Science, 270(1–2), 895–911.9Fonte 9Hearn, R. A., & Demaine, E. D. (2005). PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1–2), 72–96.

O OutBrick pertence à família em que blocos precisam sair do tabuleiro, com uma variação: cada peça tem um destino próprio. Ela só sai pela porta da sua cor e, hoje, também pode trocar de lugar com uma vizinha para alinhar três da mesma cor. Resolver o tabuleiro exige encontrar uma ordem de movimentos, como nos jogos de Hardy e Yoshigahara.

Os jogadores de 1880 teriam invejado as ferramentas atuais. Um solucionador verificou cada um dos 2.000 tabuleiros do OutBrick antes da publicação, para que ninguém encontre uma troca impossível entre 14 e 15. Nosso guia como resolver quebra-cabeças de blocos deslizantes apresenta estratégias; você também pode experimentar um tabuleiro no navegador.

• Fim da década de 1870: blocos deslizantes em um quadro aparecem em patentes dos Estados Unidos.
• Fim de 1879: o quebra-cabeça de 15 peças é vendido; Johnson e Story provam que metade das posições não tem solução.
• 1880: a febre do quebra-cabeça de 15 peças se espalha pelos Estados Unidos e pela Europa.
• 1891: Sam Loyd afirma pela primeira vez que inventou o jogo.
• 1907–1912: a patente de Hardy descreve o quebra-cabeça de tirar um bloco.
• 1996: Rush Hour é lançado nos Estados Unidos.
• 2002–2005: Rush Hour e os quebra-cabeças gerais de blocos deslizantes são demonstrados PSPACE-completos.