Como centenas de fases de quebra-cabeça são geradas e verificadas

Por Nesim Razon, desenvolvedor Android independente · 2026-11-10

Desenhar à mão um jogo de quebra-cabeça com 300 ou 400 fases levaria meses, e uma única fase impossível de resolver destrói a confiança do jogador. Deixamos o computador construir as fases e depois provamos que cada uma pode ser resolvida. É assim que isso funciona nos nossos jogos.

Dois programas: um gerador e um resolvedor

Quase todo quebra-cabeça gerado precisa de dois pedaços de código. O gerador propõe uma fase: uma disposição de paredes, peças ou dicas. O resolvedor joga a fase sozinho e informa se ela pode ser concluída, em quantos movimentos e, às vezes, de quantas maneiras diferentes.

O mais importante dos dois é o resolvedor. O gerador pode ser descuidado, porque tudo o que ele produz é verificado. Uma fase só entra no jogo se o resolvedor confirmar que ela funciona. Em vários dos nossos jogos, o resolvedor é uma simples busca em largura sobre todas as posições que o quebra-cabeça pode alcançar, lenta em um quebra-cabeça grande, mas exata em um tabuleiro pequeno.

O resolvedor também dá algo que um testador humano não dá: um número. O comprimento da solução mais curta mede o tamanho do quebra-cabeça e é o ponto de partida para avaliar a dificuldade.

Ir de trás para frente a partir de um tabuleiro resolvido

Adivinhar uma disposição aleatória e torcer para que seja resolvível desperdiça muito trabalho. Um jeito mais inteligente é partir do estado final e desfazer movimentos. Se cada passo que você dá para trás é um movimento legal jogado ao contrário, a posição a que você chega com certeza é resolvível: basta jogar os movimentos de novo para a frente.

O Beamies foi projetado assim. O gerador constrói um candidato resolvível trabalhando de trás para frente, e o resolvedor é usado principalmente para medir a dificuldade. O Nudgelings usa a mesma ideia no modo de empurrar caixas: gera as fases jogando ao contrário, puxando em vez de empurrar, de modo que a fase é resolvível por construção. O modo de veículos deslizantes segue outro caminho: o gerador examina todas as posições ligadas a uma disposição inicial e busca de trás para frente a partir das saídas, o que dá a solução mais curta exata de todas as posições de uma vez.

Trabalhar de trás para frente dá uma garantia, mas não dá um bom quebra-cabeça. Uma fase feita com poucos passos inversos aleatórios costuma ser fácil demais. É aí que entra a medição.

Medir a dificuldade

A dificuldade não tem uma definição única, mas algumas medidas funcionam bem. A mais simples é o comprimento da solução mais curta. O que é mais longo costuma parecer mais difícil, porque há mais movimentos a acertar e mais lugares para errar.

No Beamies medimos o número mínimo de arrastos com uma busca que encontra a solução mais barata. As fases recebem uma meta para esse número que cresce com a fase, com um leve dente de serra dentro de cada mundo: uma fase mais fácil depois de uma difícil e uma mais difícil no fim. O Nudgelings tem um plano parecido. As fases de veículos deslizantes miram cerca de 3 movimentos no começo, 10 perto da fase 20 e mais de 40 perto do fim das 200 fases, e o modo de empurrar tem sua própria curva, mais baixa, medida em empurrões.

Outras medidas captam algo diferente. O Grumblings analisa o grafo completo de posições e verifica, por exemplo, quantas das posições alcançáveis são becos sem saída e com que frequência o monstro fica perto do herói. Uma fase em que a maioria dos caminhos é armadilha parece muito diferente de outra em que quase todos são seguros, mesmo que a solução mais curta tenha o mesmo tamanho.

O Logiclings tem um avaliador para os quebra-cabeças de coroas que os resolve com os tipos de raciocínio que uma pessoa usa, desde uma única casa possível até testar um palpite e encontrar uma contradição. O quebra-cabeça recebe o menor nível de técnica que basta para resolvê-lo.

Subida de encosta: melhorar uma fase com pequenas mudanças

Uma fase aleatória costuma ser fácil. Para obter fases mais difíceis usamos a subida de encosta. Pegue uma fase, mude uma coisa pequena, como mover uma parede, um alienígena ou um veículo, e meça de novo. Se a fase ficou mais difícil, mantenha a mudança. Se não, descarte. Repita centenas de vezes.

É simples e funciona. No Beamies, a solução mais curta de um candidato típico passou de 4 arrastos para algo entre 10 e 19 depois de algumas centenas de passos de subida. O Nudgelings acrescentou a mesma ideia aos seus dois modos quando as primeiras fases se mostraram planas demais para os jogadores. O Logiclings usa uma versão nos quebra-cabeças de coroas: o gerador move as divisas entre regiões no sentido que deixa menos soluções, até o quebra-cabeça ter exatamente uma.

A subida tem um limite. Ela pode ficar presa em uma colina pequena quando existe uma fase melhor bem longe, e uma fase pode ficar difícil de um jeito chato, por exemplo com uma longa sequência forçada. Por isso também escolhemos entre vários candidatos e olhamos os resultados em um aparelho de verdade.

Uma única resposta: unicidade

Alguns quebra-cabeças precisam ter exatamente uma solução; caso contrário, o jogador pode fazer tudo certo e ainda ouvir que errou. É o caso de vários dos nossos quebra-cabeças de lógica. O resolvedor é escrito para contar soluções e para assim que encontra uma segunda.

O Logiclings constrói o quebra-cabeça de duas cores a partir de um tabuleiro completo e depois remove dicas e marcas uma a uma, mantendo cada remoção apenas se o resolvedor ainda encontrar uma única resposta. O quebra-cabeça de caminho começa com um percurso completo por todas as casas, depois mantém só os números necessários para que esse percurso seja o único e acrescenta alguns extras nos ajustes fáceis.

Repare que unicidade e dificuldade puxam em direções opostas. Menos dicas deixam o quebra-cabeça mais difícil, mas dicas demais a menos perdem a resposta única. O resolvedor é o que nos permite chegar até a beira desse limite.

Gerar antes e verificar cada fase

Gerar uma fase difícil pode ser lento. No Beamies, criar algumas fases avançadas com o jogo em execução levava mais de 8 segundos, tempo demais para fazer o jogador esperar. Por isso as 400 fases são construídas antes em um computador e guardadas no aplicativo como um arquivo. Cada celular carrega então exatamente as mesmas fases na hora. O Grumblings faz o mesmo com as suas 300 fases, que são geradas juntas em menos de um minuto e escolhidas de um conjunto de candidatos pela pontuação de dificuldade.

Nada entra sem verificação. Um teste no Grumblings abre todas as fases do pacote e reproduz a solução guardada com as regras reais do jogo, e um teste no Nudgelings verifica os seus dois pacotes com o resolvedor. Se uma fase falha, a compilação falha. Se as regras mudam, o pacote é gerado de novo.

A última verificação é humana. Um computador pode dizer que uma fase é resolvível e qual é o seu tamanho. Ele não pode dizer se ela é divertida. Jogamos as fases em um celular, e é ali que a curva é ajustada.

Erros que cometemos

Medir nos ajudou a encontrar problemas reais. Em um teste inicial com jogadores do Nudgelings, viu-se que as fases de veículos não pareciam mais difíceis até a fase 27, então o pacote inteiro foi gerado de novo com uma curva mais íngreme e novas mecânicas.

Os resolvedores também precisam de limites. Uma busca que não dá problema na geração pode esgotar a memória em um celular. Uma dica e uma verificação de travamento do Beamies usavam um resolvedor sem limite de memória, e uma fase grande o derrubou. Hoje executamos essas buscas com um orçamento.

Um quebra-cabeça gerado vale o que vale a regra que ele mede. Se você mede a coisa errada, constrói uma máquina muito eficiente que produz as fases erradas.