O que é o Quebra-Cabeça 15?

O Quebra-Cabeça 15 (15-puzzle) é um sliding puzzle inventado em 1880 por Noyes Chapman. 15 peças numeradas em uma grade 4x4 com um espaço vazio. Você desliza peças adjacentes ao vazio pra reorganizar e colocar todas em ordem (1-15 lendo esquerda pra direita, cima pra baixo). E um clássico da teoria dos algoritmos.

Qualquer embaralhamento tem solucao?

Não! Apenas metade das 16!/2 = 10 trilhoes de configuracoes são soluveis. Felizmente, nosso embaralhamento e GARANTIDO solucionavel — geramos posições aleatorias aplicando 1000 movimentos validos a partir da posição resolvida, então toda partida tem solucao.

Quantos movimentos no mínimo?

Depende do embaralhamento. A configuracao mais difícil possivel precisa de 80 movimentos (provado por busca exaustiva em 2010). Embaralhamentos aleatorios tipicamente precisam de 50-60 movimentos otimos. Pessoas comuns chegam em 100-150 movimentos.

Por que e considerado NP-difícil?

Encontrar o NÚMERO MÍNIMO de movimentos pra resolver o 15-puzzle generalizado (NxN) é NP-difícil. Pra 4x4 é factível computar (IDA*), mas pra 5x5 já fica intratável. E um problema academicamente estudado em algoritmos de busca.

Quebra-Cabeça 15

Sliding puzzle 4x4 — ordene as pecas 1 a 15

Médio ~4 min 153 Grátis

Como jogar

Toque numa peca adjacente ao vazio pra desliza-la
Objetivo: organizar 1-15 em ordem
Movimentos contados
Tempo cronometrado
Recordes de moviments + tempo separados

Sobre o Quebra-Cabeça 15

Quebra-Cabeça 15 (também conhecido como Jogo dos 15, Sliding Puzzle ou Mystic Square) e um clássico inventado em 1880. 15 pecas numeradas em uma grade 4x4 com um espaco vazio. Você desliza pecas adjacentes ao vazio para reorganiza-las na ordem correta (1-15 lendo esquerda pra direita, cima pra baixo).

Parece simples? E um problema NP-difícil — até matematicos demoram. Seus recordes de tempo e movimentos são salvos.