O 8-puzzle ocupa muito pouco espaço e tem uma reputação desproporcional. Oito peças quadradas, numeradas de 1 a 8, num tabuleiro 3×3. Uma célula está vazia. A sua tarefa: faz-se deslizar peças para o espaço vazio, um movimento de cada vez, até os números ficarem em ordem — habitualmente 1‑2‑3 em cima, 4‑5‑6 ao meio, 7‑8‑vazio em baixo.
É o membro mais pequeno da família dos N-puzzles. O 15-puzzle é o primo mais conhecido, mas o 8-puzzle é por onde a maior parte — crianças, estudantes e investigadores de algoritmos de busca — costuma começar.
Como funciona um movimento
A célula vazia é a única coisa que verdadeiramente se controla. Só pode deslizar uma peça que esteja diretamente acima, abaixo, à esquerda ou à direita do espaço vazio. Movimentos diagonais não são permitidos. Pegar nas peças e largá-las algures também não. Cada movimento é uma única peça vizinha que desliza uma célula para o espaço vazio, e o espaço vazio passa a ocupar o lugar que essa peça tinha.
Essa regra minúscula é o que torna o puzzle interessante. Tem sempre a sensação de que há só um ou dois movimentos úteis, e ainda assim um tabuleiro 3×3 esconde 181 440 disposições solúveis distintas. (A outra metade — as insolúveis — é assunto de um guia separado sobre paridade.)
A estratégia manual padrão
O truque a que a maioria chega, e que escala até 4×4, 5×5 e além, é este:
- Resolva a linha de cima primeiro — coloque o 1, o 2 e o 3 e nunca mais lhes toque.
- Resolva a coluna da esquerda a seguir — coloque o 4 e o 7. Agora a linha de cima e a coluna da esquerda estão travadas.
- O 2×2 restante — três peças e um espaço — tem exatamente dois estados: resolvido, ou uma peça fora de lugar. Se estiver uma peça fora, não consegue arranjá-lo dentro do 2×2 sozinho a partir de uma posição inicial solúvel; precisa de voltar ao resto do puzzle. (É por isso que a paridade importa.)
A parte difícil é colocar a última peça de cada linha ou coluna. Para pôr o 3 no canto superior direito, normalmente é preciso primeiro deslizar o 2 para o canto superior direito, depois trazer o 3 para baixo dele, e depois rodar o par para a posição. Esta pequena manobra em "L" é o mesmo movimento que vai usar no 15-puzzle, no 24-puzzle e em qualquer outro tamanho.
As soluções ótimas são curtas
O 8-puzzle mais difícil possível resolve-se em 31 movimentos. Isto é em todas as 181 440 posições iniciais — a pior não está a mais do que 31 deslizes da solução.
Uma posição média exige cerca de 22 movimentos. Um computador a usar A* com uma boa heurística encontra a resposta ótima em microssegundos. À mão, quem conhece a estratégia da linha de cima resolve qualquer 8-puzzle bem abaixo de um minuto, assim que detete o padrão.
Por que os cientistas de computação gostam dele
O 8-puzzle é o benchmark introdutório padrão para busca heurística. O tabuleiro é pequeno o suficiente para enumeração exaustiva, grande o suficiente para que a força bruta seja desperdiçada, e rico o suficiente para mostrar a diferença entre duas heurísticas bem conhecidas:
- Peças mal colocadas — contar quantas não estão no lugar. Barato, mas guia fraco.
- Distância de Manhattan — para cada peça, somar a distância em linha e em coluna até ao alvo. Guia mais forte, ainda barato.
Uma implementação de A* de manual com Manhattan resolve qualquer 8-puzzle em microssegundos. Passe ao 15-puzzle e precisa de bases de padrões aditivas para manter a rapidez — é uma conversa maior, e vive no guia do solver do 15-puzzle.
Quando jogar o 8-puzzle
Um tabuleiro 3×3 é um prazer tranquilo. Não há muitos movimentos para pensar, a condição de vitória é óbvia, e terminar um leva um minuto ou dois. É o tamanho certo para:
- Uma criança a aprender o que é "planear um movimento à frente".
- Um adulto no autocarro que não quer um puzzle longo nas mãos.
- Uma ronda de treino antes de subir para o 15-puzzle.
É também o tamanho que costuma estar quase sempre gratuito nas apps de quebra-cabeças deslizantes, incluindo a nossa — os tabuleiros maiores costumam ficar atrás de paywalls porque geram sessões mais longas, mas o 3×3 é o onboarding de toda a gente.
O que muda no 4×4
Tudo o que é estratégia mantém-se igual. Resolve-se a linha de cima, depois a coluna da esquerda, depois recorre-se no 3×3 que sobra. O que muda é o tempo: um 8-puzzle em 30 segundos torna-se um 15-puzzle em 5–10 minutos. Os números pioram a partir daí — os tamanhos 5×5 e 6×6 exigem paciência a sério.
Se os 8-puzzles começarem a aborrecer ao fim de uma semana, é o sinal para subir.