Jogo dos quinze

Sobre este teste

O jogo dos quinze é um quebra-cabeça mecânico que apareceu na segunda metade do século XIX: um quadro, quinze peças numeradas, uma casa vazia, e como único movimento o deslizamento de uma peça vizinha do buraco. Virou moda internacional considerável nos anos 1880, alimentada por desafios públicos que prometiam recompensa pela resolução de certas posições.

Esses desafios eram armados, e o motivo é matemático: só metade dos arranjos possíveis é alcançável. A operação elementar do jogo nunca permite simplesmente trocar duas peças entre si, de modo que um embaralhamento em cada dois é estritamente insolúvel. A grade oferecida aqui é sempre gerada a partir da posição resolvida por uma sequência de movimentos legais, então ela sempre tem solução.

O método que funciona é hierárquico, e é justamente o contrário da intuição. Não se empurram as peças para os seus lugares uma a uma: termina-se a primeira fileira por completo, proíbe-se mexer nela, depois a segunda, e resolvem-se as duas últimas juntas, trabalhando em colunas de duas. Quem passa de trezentos lances é quase sempre quem desmonta uma fileira já pronta para ganhar uma peça.

Como funciona

Contamos o número de deslizamentos até a ordem completa de 1 a 15, com a casa vazia no canto de baixo à direita. Desistir conta como derrota e vale zero. Para uma grade resolvida, a nota de 0 a 100 parte de 400 lances e chega ao máximo em 60 lances.