Como criamos níveis de pentominós com Dancing Links

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

Cada nível de Encaixar no Pentolings é uma promessa: existe um jeito de preencher esta forma com estas peças. Para cumpri-la em 150 níveis, e para dar uma dica a qualquer momento, o jogo traz dentro um pequeno resolvedor baseado nos Dancing Links de Donald Knuth. Aqui explicamos como ele funciona com um exemplo minúsculo que qualquer pessoa consegue acompanhar.

Um quebra-cabeça de pentominós é um problema de cobertura exata

Veja um nível como uma lista de regras. Cada peça precisa ser usada exatamente uma vez. Cada quadrado da forma precisa ser coberto exatamente uma vez. Nada pode se sobrepor e nada pode sobrar. Um problema feito de regras assim se chama problema de cobertura exata, e muitos quebra-cabeças acabam sendo exatamente isso, do sudoku ao planejamento de horários.

Para que um computador o resolva, escrevemos o problema como uma tabela. Cada coluna é uma regra: uma coluna para cada peça e uma coluna para cada quadrado da forma. Cada linha é uma jogada possível: uma peça específica, girada de um jeito específico e colocada em um lugar específico. A linha marca as colunas que cumpre: a coluna da própria peça e os cinco quadrados que ela cobriria. O quebra-cabeça está resolvido quando você escolhe linhas de modo que cada coluna seja marcada exatamente uma vez.

63 posições: as linhas da tabela

Um pentominó pode ser girado e virado, então primeiro o jogo lista todas as posições diferentes de cada uma das doze peças. Ele gira e espelha a forma e guarda apenas os resultados realmente novos. O X dá 1 posição, o I dá 2, o T, o U, o V, o W e o Z dão 4 cada, e o F, o L, o N, o P e o Y dão 8 cada. Isso soma 63 posições para o conjunto todo, um número que o código confere.

Depois, para a forma do nível, ele desliza cada posição para todos os lugares em que os cinco quadrados ficam dentro da forma. Para um retângulo 3x20 com as doze peças, isso dá 1236 linhas candidatas. Para o maior nível, um retângulo 6x10, são 2056. A tabela tem 72 colunas: 12 peças mais 60 quadrados.

Um exemplo minúsculo

Pegue um retângulo 3x5 e as peças P, U e V. A tabela tem 3 colunas de peça e 15 de quadrado, ou seja, 18 colunas ao todo. As peças têm 40, 20 e 12 colocações possíveis, o que dá 72 linhas. Ao escolher três linhas que marquem cada coluna exatamente uma vez, aparece a resposta: o V nas bordas esquerda e inferior, o U à direita e o P no meio. Em texto, as três linhas do tabuleiro ficam VPPUU, VPPPU e VVVUU. Girar ou espelhar o retângulo inteiro dá quatro versões da mesma resposta, então o resolvedor encontra quatro soluções que parecem a mesma para uma pessoa.

Os Dancing Links de Knuth, em palavras simples

A busca é o Algoritmo X. Escolha uma coluna que ainda não foi coberta. Experimente cada linha que a marca. Escolher uma linha significa que as outras colunas dela já foram usadas, então toda linha que conflita com ela pode ser descartada. Depois, repete-se com a tabela menor. Se alguma coluna ficar sem linhas, você escolheu errado antes, então volta e tenta a próxima linha.

O truque inteligente é como a tabela é guardada. Donald Knuth percebeu que as marcas podem ficar em listas encadeadas, em que cada marca aponta para a vizinha da esquerda, da direita, de cima e de baixo. Remover uma linha é apenas redirecionar alguns elos, e o item removido continua lembrando onde estava, então recolocá-lo é refazer os passos ao contrário. Como os nós parecem sair e voltar, ele chamou a técnica de Dancing Links, elos dançantes. No Pentolings, o Dlx.kt tem cerca de oitenta linhas e trabalha com vetores de inteiros simples para ganhar velocidade.

Mais um truque: a cada passo o resolvedor escolhe a coluna com menos linhas restantes. Se um quadrado só pode ser coberto de duas maneiras, a busca testa logo essas duas em vez de vagar pela tabela. É a versão de computador do que dissemos no guia: comece pelos lugares apertados.

Peças com cadeado e níveis justos

Alguns níveis do Pentolings começam com uma peça com cadeado. Essas peças vêm de uma solução real: o gerador encontra uma resposta e depois congela uma ou duas de suas peças. O resolvedor as trata como já escolhidas, retira seus quadrados e colunas da tabela e conta o que sobra.

Fazer um nível é mais do que resolver. Um gerador monta um contorno colocando as peças lado a lado ao acaso, então por construção existe uma solução. Depois ele pontua muitos contornos: premia formas compactas, penaliza buracos, premia simetria e prefere formas com mais respostas nos primeiros níveis. Como contornos feitos assim costumam ter exatamente uma solução, a dificuldade vem principalmente do número de peças e do formato estranho do contorno. Cada um dos 150 níveis é resolvido de novo nos testes, verifica-se que não há duplicados (uma cópia girada ou espelhada conta como a mesma) e o último nível, um retângulo 6x10, é o único lugar com uma quantidade enorme de respostas. Um teste também confirma o número clássico para 3x20: oito, que são as duas respostas verdadeiras vezes as quatro maneiras de girar ou espelhar o retângulo.

Por que não tentar tudo de uma vez?

Você poderia resolver um quebra-cabeça testando cada peça em cada posição, uma após a outra, e conferindo no final. Isso não funciona, nem para um computador. Com doze peças, 63 posições e dezenas de lugares, o número de combinações é astronômico, e quase todas se sobrepõem ou deixam vãos nas primeiras jogadas.

O truque é parar um ramo ruim assim que se vê que ele é ruim. O Algoritmo X faz exatamente isso. No momento em que um quadrado fica sem nenhuma peça que possa cobri-lo, a busca deixa de aprofundar e volta. Os Dancing Links tornam cada volta barata. É por isso que um tabuleiro 6x10, com 2056 colocações candidatas, é resolvido rápido até em um celular, e é por isso que o botão de dica não precisa de servidor.

O que aprendemos

A mesma lógica do resolvedor existe duas vezes: em Python, onde o gerador monta e confere o pacote de 150 níveis, e em Kotlin, que vai no aplicativo. Os testes em Kotlin resolvem de novo, do zero, cada nível do pacote. Com duas implementações independentes, é pouco provável que um erro em uma se esconda da outra.

A maior surpresa foi como é raro um contorno aleatório ter mais de uma resposta. Esperávamos que muitos desafios tivessem várias soluções e encontramos o contrário. Acontece que isso não é problema: os jogadores se importam que um nível seja resolvível e justo, não quantas soluções ele tem, então o jogo aceita qualquer preenchimento válido. O que o resolvedor nos dá é a promessa de que cada nível e cada dica merecem confiança.

As dicas saem do mesmo resolvedor

O botão Dica faz ao resolvedor uma pergunta nova: dadas as peças que você já colocou, como o resto se encaixa? Ele trata suas peças colocadas como fixas, resolve o que falta e destaca a próxima peça da resposta que encontrou. Se você seguir a dica, a próxima pode vir da memória sem resolver de novo. O trabalho roda em segundo plano com limite de tempo para a tela nunca travar.

Se as peças que você colocou tornam a solução impossível, o resolvedor não acha nada e o jogo avisa: sem solução daqui, retire uma peça. Assim a dica serve até quando você não está travado, apenas inseguro. E o jogo aceita qualquer jeito válido de preencher a forma, não só o que o gerador encontrou, então você nunca precisa adivinhar a resposta do autor.