O jogo do 15
O jogo do 15 é uma moldura com quinze peças numeradas e um espaço vazio. Deslize as peças de volta para a ordem e ele está resolvido. Parece simples, mas causou uma febre em 1880, e por trás dele está uma das provas mais elegantes da matemática recreativa: metade de todas as posições nunca pode ser resolvida.
A febre de 1880
O quebra-cabeça surgiu no estado de Nova York na década de 1870; Noyes Chapman, chefe dos correios em Canastota, costuma ser apontado como seu inventor. No início de 1880, ele virou uma febre, primeiro em todos os Estados Unidos e depois na Europa.
O 14-15 de Sam Loyd
O criador de quebra-cabeças americano Sam Loyd afirmou mais tarde que tinha inventado o jogo e falou de um prêmio de 1.000 dólares para quem conseguisse resolvê-lo com apenas o 14 e o 15 trocados. Ninguém ganhou o prêmio, e ninguém poderia: essa posição não tem solução. A sua alegação de ter inventado o jogo também não era verdadeira.
Por que metade das posições é impossível
Trate o espaço vazio como uma décima sexta peça. Cada deslizamento troca o espaço vazio de lugar com uma peça. Para voltar ao seu canto, o espaço vazio precisa se mover tantas vezes para a esquerda quanto para a direita e tantas vezes para cima quanto para baixo, então uma posição com o espaço vazio no canto está sempre a um número par de trocas da ordem resolvida. Trocar o 14 e o 15 é uma troca, que é ímpar, então nenhum deslizamento pode chegar a ela. Em 1879, William Johnson e William Story provaram que exatamente metade de todas as disposições pode ser alcançada.
Um teste para qualquer posição
Conte os pares de peças que estão na ordem errada quando você lê a moldura linha por linha. Em um tabuleiro 3×3 ou 5×5, uma posição tem solução quando essa contagem é par. Em um tabuleiro 4×4, some a linha do espaço vazio contada de baixo para cima: a posição tem solução quando a soma é ímpar.
Resolução por computador
Um computador pode procurar um caminho de volta com A*, que sempre examina primeiro a posição mais promissora. Ele estima os movimentos que ainda faltam pela distância de cada peça até a sua casa, mais dois movimentos para cada par de peças que se bloqueiam na própria linha ou coluna. Encontrar a solução mais curta fica muito difícil em tabuleiros grandes. As posições mais difíceis do jogo do 15 precisam de 80 movimentos, e o jogo do 8 nunca precisa de mais de 31.
Experimente no PictorX
Abra o Jogo do 15 e clique em uma peça para deslizá-la. Embaralhar mistura as peças em uma nova posição que tem solução, Resolver reproduz uma solução movimento a movimento, e Mostrar peças no lugar colore os números das peças que já estão na posição certa. Escolha “14-15 de Loyd” para ver a posição impossível e use Tamanho para alternar entre 3×3, 4×4 e 5×5.
Perguntas frequentes
Quem inventou o jogo do 15?
Noyes Chapman, chefe dos correios em Canastota, Nova York, costuma ser apontado como o inventor, na década de 1870. A alegação posterior de Sam Loyd era falsa.
O quebra-cabeça 14-15 tem solução?
Não. Ele está a uma troca da ordem resolvida, e toda posição que os deslizamentos alcançam está a um número par de trocas.
Quantas posições o jogo do 15 tem?
As 16 casas podem ser preenchidas de 20.922.789.888.000 maneiras. Exatamente metade delas, 10.461.394.944.000, pode ser alcançada deslizando as peças.
O PictorX envia alguma coisa?
Não. O quebra-cabeça é desenhado numa tela no seu navegador. Salvar baixa um PNG, e Editar abre essa imagem no editor do PictorX.
Ferramentas relacionadas
Jogo do 15
Jogue o clássico jogo do 15, o quebra-cabeça deslizante, no seu navegador, com peças de madeira em 3×3, 4×4 ou 5×5. Embaralhe, deslize linhas inteiras de uma vez, tente o impossível 14-15 de Sam Loyd ou veja Resolver terminar o jogo.
Torre de Hanói
Mova uma torre de discos entre três hastes no seu navegador. Um disco de cada vez, nunca um maior sobre um menor. A solução mais curta tem 2ⁿ − 1 movimentos.
Torre de Hanói
A Torre de Hanói: três hastes, um disco de cada vez e nunca um maior sobre um menor. A solução mais curta tem 2ⁿ−1 movimentos. Édouard Lucas apresentou o quebra-cabeças em 1883.
Passeio do cavalo
Faça um cavalo de xadrez saltar por todas as casas do tabuleiro exatamente uma vez. Jogue você mesmo com as dicas de Warnsdorff ou veja Resolver terminar um passeio aberto ou fechado. Salve o caminho como PNG.
Oito damas
Coloque oito damas em um tabuleiro de xadrez sem que nenhuma ataque outra. Tente você mesmo, veja a busca com backtracking encontrar uma solução passo a passo e percorra todas as 92 soluções.
Formiga de Langton
Execute a formiga de Langton no navegador. Veja a simetria, o caos e a autoestrada de 104 passos e depois experimente regras multicoloridas, várias formigas, uma grelha hexagonal e turmites.
Pronto para experimentar?
Abra o PictorX em seu navegador – sem instalação, sem necessidade de cartão de crédito para iniciar.
Jogar o Jogo do 15