Algoritmos

Como garantir que um Sudoku tenha solução única

Por Fernando Capanema, SpiderWorks · Publicado em 22 de outubro de 2026

Um Sudoku bem formado tem exatamente uma solução. Parece um detalhe acadêmico até o jogo marcar como errada uma resposta que respeita todas as regras. Foi o que levou à reescrita do gerador do Sudoku Pro.

O gerador da versão 1.0.1

A versão enviada para revisão construía a solução de cada fase com uma fórmula de deslocamento:

return ((row * 3 + Math.floor(row / 3) + col + level - 1) % 9) + 1;

A fórmula sempre gera uma grade válida: cada linha é a anterior deslocada, com saltos nos limites dos blocos. Depois, um conjunto de casas embaralhado com uma semente da fase era mantido como pistas (de 50 na fase 1 a 26 na fase 100) e o restante ficava vazio. O jogo comparava cada número digitado com a solução da fórmula.

Há dois problemas. Primeiro, todas as fases são variações da mesma grade, apenas com os dígitos trocados em ciclo; um jogador atento percebe o padrão. Segundo, nada garantia que as pistas mantidas determinassem uma única resposta.

A medição

Para saber se o segundo problema era teórico, reproduzimos o gerador antigo fora do aplicativo e passamos cada uma das 100 fases por um contador de soluções. O resultado, obtido em 22/10/2026: 70 das 100 fases admitiam mais de uma solução, a primeira delas já na fase 4. Em cada uma, um jogador poderia preencher uma casa com um dígito que não viola nenhuma regra e ver o jogo marcá-lo como erro.

A causa é estrutural. Grades geradas por deslocamento têm muitas simetrias; retângulos de casas cujos valores podem ser trocados entre si sem quebrar as regras aparecem com frequência, e retirar pistas ao acaso raramente elimina todos eles.

O novo gerador

A revisão em desenvolvimento separa o processo em duas etapas, ambas guiadas por um gerador pseudoaleatório com semente da fase:

1. Grade completa aleatória. Um backtracking percorre as 81 casas e tenta os dígitos em ordem embaralhada, voltando quando uma casa fica sem opção. Isso produz grades realmente diferentes entre fases.
2. Retirada com verificação. As casas são visitadas em ordem aleatória. Cada uma é esvaziada provisoriamente, e o resolvedor conta as soluções do tabuleiro resultante. Se houver mais de uma, a casa volta a ser preenchida.

for (const index of shuffled(allCells, rng)) {
  if (clues <= target) break;
  const keep = puzzle[index];
  puzzle[index] = 0;
  if (countSolutions(puzzle, 2) !== 1) puzzle[index] = keep;
  else clues--;
}

O contador de soluções

O ponto que torna a abordagem viável no celular é que não é preciso contar todas as soluções: basta saber se existe uma segunda. O contador recebe um limite (2) e interrompe a busca assim que o atinge.

Duas técnicas deixam a busca rápida:

• Máscaras de bits. Para cada linha, coluna e bloco há um inteiro de 9 bits com os dígitos já usados. Os candidatos de uma casa são 511 & ~(linha | coluna | bloco), uma operação, e uma tabela pré-calculada dá a quantidade de bits ligados.
• Casa mais restrita primeiro. A cada passo, a busca escolhe a casa vazia com menos candidatos. Se alguma tem zero, o ramo é abandonado; se tem um, o valor é forçado sem ramificação. Essa heurística reduz a árvore de busca em ordens de grandeza em relação a percorrer as casas em ordem.

const mask = 511 & ~(rows[ROW(i)] | cols[COL(i)] | boxes[BOX(i)]);
const c = BIT_COUNT[mask];
if (c === 0) return;               // contradição
if (c < bestCount) { best = i; bestMask = mask; bestCount = c; if (c === 1) break; }

Pistas e dificuldade

O alvo de pistas cai linearmente de 42 na fase 1 para 25 na fase 100. É um alvo, não uma garantia: se a verificação rejeitar retiradas demais, o tabuleiro pode terminar com mais pistas. Na medição, todas as 100 fases atingiram exatamente o alvo.

Vale registrar uma limitação honesta: o número de pistas é um indicador aproximado de dificuldade. Dois Sudokus com 25 pistas podem exigir técnicas muito diferentes. Classificar pela técnica mais avançada necessária para resolver por dedução seria mais preciso e é uma evolução possível; por enquanto, as fases são nomeadas pela posição (Fácil até 20, Médio até 45, Difícil até 75 e Especialista daí em diante).

Sementes e progresso salvo

A semente combina o número da fase e um contador de ciclo (o jogo recomeça na fase 1 depois da 100, com outro ciclo). Como a geração é determinística, o jogo não precisa guardar o tabuleiro: salva só o que o jogador digitou, as anotações e as dicas, e regenera a grade ao abrir. O progresso salvo é validado contra a grade regenerada antes de ser aplicado.

Resultados

Medição feita em 22/10/2026 em um computador de desenvolvimento com Node.js 24, gerando as 100 fases em sequência: média de 0,4 ms por fase e máximo de 2,6 ms. As 100 fases passaram na verificação de solução única. Em celulares o tempo será maior, mas a margem é ampla. Os valores da primeira fase incluem o aquecimento do compilador JavaScript.

Lições

• “Parece funcionar” não é verificação. A falha da versão 1.0.1 só ficou clara ao medir todas as fases.
• Para propriedades que valem para todo o conteúdo gerado, um teste que percorre todo o conteúdo é barato e decisivo.
• Perguntar “existe uma segunda?” é muito mais barato que “quantas existem?”.
• Geração determinística por semente simplifica salvar, reproduzir e investigar relatos de jogadores.