O Sudoku usa números, mas não é um quebra-cabeça de aritmética.
Você nunca precisa calcular uma soma, produto ou fórmula numérica para resolver uma grade clássica.
Os dígitos 1–9 funcionam principalmente como nove símbolos distintos.
O que torna o Sudoku matematicamente interessante é a estrutura ao redor desses símbolos:
- combinatória;
- quadrados latinos;
- satisfação de restrições;
- cobertura exata;
- relações de conflito semelhantes a grafos;
- simetria;
- busca;
- enumeração.
Essa estrutura ajuda a explicar tanto por que o Sudoku é fácil de definir quanto por que seu espaço de soluções é enorme.
Sudoku como quadrado latino com restrições
Um quadrado latino de ordem 9 é um arranjo 9×9 de nove símbolos no qual cada símbolo aparece exatamente uma vez em cada linha e coluna.
Uma grade completa de Sudoku clássico satisfaz essas duas condições mais a condição dos blocos 3×3.
Portanto:
Toda grade completa de Sudoku clássico é um quadrado latino com restrições adicionais de bloco.
Mas:
Nem todo quadrado latino 9×9 é uma grade válida de Sudoku.
Essa relação é matematicamente importante.
Historicamente, porém, ela não deve ser transformada na frase incorreta:
“Euler inventou o Sudoku.”
Quadrados latinos fazem parte do contexto matemático.
A história direta do quebra-cabeça moderno é tratada separadamente em História do Sudoku.
Satisfação de restrições
O Sudoku é um exemplo natural de problema de satisfação de restrições.
Pense em cada célula como uma variável.
No início, uma célula vazia pode ter um domínio como:
{1,2,3,4,5,6,7,8,9}
As pistas e as relações entre células reduzem esses domínios.
Exemplo:
candidatos de r4c7
{2,5,8}Se um novo 8 aparecer em uma de suas unidades relacionadas:
{2,5,8}
↓
{2,5}Se depois o 2 for eliminado:
{2,5}
↓
{5}A célula fica resolvida.
A notação humana de candidatos é, portanto, uma forma muito legível de redução de domínio e propagação de restrições.
Sudoku como cobertura exata
O Sudoku clássico também pode ser expresso como um problema de cobertura exata.
Uma atribuição completa precisa satisfazer requisitos como:
- cada célula recebe exatamente um dígito;
- cada linha contém cada dígito exatamente uma vez;
- cada coluna contém cada dígito exatamente uma vez;
- cada bloco contém cada dígito exatamente uma vez.
No Sudoku clássico 9×9, as possíveis colocações podem ser representadas em relação a essas restrições de cobertura exata.
Algoritmos como Algorithm X e implementações como Dancing Links são, por isso, formas naturais de resolver Sudoku computacionalmente.
O jogador não precisa aprender cobertura exata.
Para software, ela é útil porque oferece outra maneira de realizar resolução completa e contagem de soluções.
Sudoku como problema semelhante a um grafo
Outro ponto de vista trata células ou estados de candidatos como nós conectados por conflitos.
No nível simples das células:
Duas células relacionadas não podem conter o mesmo dígito.
Isso lembra um problema estruturado de coloração de grafos:
- as células são variáveis/nós;
- os dígitos são rótulos/cores;
- as relações entre células impõem exclusões.
Grafos no nível dos candidatos são ainda mais úteis para:
- Enlaces Fortes;
- Enlaces Fracos;
- Colorização;
- Cadeias.
O jogador não precisa de teoria dos grafos para resolver um Sudoku comum, mas essa conexão explica por que técnicas avançadas podem ser representadas como redes de relações lógicas.
Busca e backtracking
Um solucionador genérico também pode usar busca recursiva.
Um esquema simples:
- escolha uma célula não resolvida;
- selecione um candidato;
- propague as restrições;
- continue recursivamente;
- se o estado se tornar impossível, faça backtracking;
- tente outro candidato.
Com boas heurísticas, isso resolve Sudokus padrão 9×9 de forma muito eficiente.
Mais importante: uma busca completa consegue responder perguntas que um analisador de técnicas humanas não foi projetado para responder diretamente:
Existe alguma solução?
Existe uma segunda solução?
Isso torna a busca completa útil como uma camada de validação, mesmo que o jogador nunca a veja.
Quantas grades completas de Sudoku existem?
Para o Sudoku clássico 9×9, Bertram Felgenhauer e Frazer Jarvis calcularam:
6.670.903.752.021.072.936.960
grades solução completas e válidas.
Aproximadamente:
6,671 × 10²¹
São mais de seis sextilhões de grades completas.
A contagem considera como diferentes muitas grades que são estruturalmente equivalentes por transformações.
Grades essencialmente diferentes
Transformações que preservam o Sudoku podem converter uma grade completa válida em outra.
Exemplos incluem:
- renomear os dígitos de forma consistente;
- trocar linhas dentro de uma banda;
- trocar colunas dentro de uma pilha;
- trocar bandas inteiras;
- trocar pilhas inteiras;
- transposição;
- rotações/reflexões apropriadas.
Depois de considerar o grupo padrão de simetrias do Sudoku, o número clássico de grades completas essencialmente diferentes é:
5.472.730.538
Ainda mais de cinco bilhões.
A contagem exata depende de quais transformações são consideradas equivalentes; o valor 5.472.730.538 usa o grupo padrão de simetrias do Sudoku.
Por que essas contagens não são o número de quebra-cabeças Sudoku
Uma grade completa é uma grade solução.
Um quebra-cabeça é um subconjunto de pistas que aponta para uma solução sob as condições editoriais desejadas.
Uma mesma grade solução pode suportar muitos conjuntos diferentes de pistas.
Esses conjuntos podem diferir em:
- número de soluções;
- minimalidade;
- simetria das pistas;
- dificuldade;
- caminho de resolução humana;
- qualidade estética.
Portanto, o número de possíveis quebra-cabeças não é simplesmente o número de grades solução.
A geração acrescenta outra enorme camada combinatória.
Simetria na construção de Sudokus
Vale separar duas ideias de simetria.
Simetria matemática
Transformações que preservam validade ou equivalência do Sudoku.
Simetria na disposição das pistas
O criador escolhe pistas em um padrão visualmente simétrico — frequentemente com simetria rotacional.
A segunda é uma escolha estética ou editorial.
Ela não é exigida pelas regras clássicas.
Historicamente, a Nikoli adotou pistas simétricas como parte de seu estilo de construção, mas um Sudoku assimétrico ainda pode ser perfeitamente válido.
Combinatória e seleção de pistas
Suponha que começamos com uma solução completa.
Existem 81 posições de células.
Cada conjunto possível de pistas seleciona algum subconjunto dessas posições.
Mas a maioria dos subconjuntos não é adequada para publicação.
Um conjunto alvo de pistas pode precisar satisfazer:
- consistência;
- unicidade;
- minimalidade opcional;
- resolubilidade humana;
- dificuldade desejada.
Por isso a geração de Sudoku não pode ser reduzida a:
Escolher N células aleatórias.
O espaço combinatório é gigantesco, enquanto o espaço de bons Sudokus publicáveis é muito mais estreito.
Mínimo de pistas como problema extremo
O resultado das 17 pistas responde a outra pergunta matemática:
Até onde um conjunto de pistas único pode ser reduzido?
A prova de que não existe Sudoku único com 16 pistas exigiu computação exaustiva e uma formulação por hitting sets.
É um exemplo de como o Sudoku conecta design de quebra-cabeças recreativos com busca combinatória séria.
Dificuldade como problema de computação humana
O tamanho matemático do problema, por si só, não descreve a dificuldade do Sudoku.
Todos os Sudokus clássicos compartilham:
- 81 células;
- 9 dígitos;
- as mesmas três famílias de unidades.
Mesmo assim, a dificuldade humana varia muito.
Pesquisas que compararam métricas de dificuldade com dados de jogadores encontraram dois componentes importantes:
- complexidade dos passos individuais;
- estrutura de dependências entre esses passos.
Isso lembra que dificuldade é, em parte, um modelo de cognição e busca humana, não apenas uma propriedade estática como número de pistas.
Por que diferentes solucionadores de Sudoku têm funções diferentes
Os diferentes pontos de vista matemáticos explicam por que um software de Sudoku costuma separar várias tarefas.
Solucionador completo / contador de soluções
Métodos possíveis:
- backtracking;
- cobertura exata;
- SAT/CSP.
Responsabilidades:
- validade;
- existência de solução;
- unicidade.
Solucionador de estilo humano
Responsabilidades:
- caminho de deduções nomeadas;
- candidatos;
- técnicas;
- metadados de explicação.
Gerador
Responsabilidades:
- criar/selecionar uma grade solução;
- escolher pistas;
- chamar a validação de unicidade;
- chamar a análise humana;
- satisfazer restrições editoriais ou de construção.
Uma única representação não precisa atender todas as tarefas com a mesma eficiência.
Perguntas frequentes
Sudoku é baseado em aritmética?
Não. Os dígitos funcionam como símbolos.
Todo Sudoku é um quadrado latino?
Toda grade completa de Sudoku clássico é um quadrado latino com a restrição adicional dos blocos.
Todo quadrado latino é uma grade de Sudoku?
Não.
Quantas grades completas de Sudoku clássico existem?
6.670.903.752.021.072.936.960.
Por que existem “apenas” cerca de 5,47 bilhões de grades essencialmente diferentes?
Porque muitas grades completas são equivalentes sob simetrias que preservam o Sudoku.
O enorme número de soluções torna um Sudoku difícil?
Não diretamente. A dificuldade humana depende das pistas específicas e do caminho de deduções.
O que aprender depois
Leia Como Sudokus São Gerados para ver como grades solução matemáticas se transformam em quebra-cabeças jogáveis.
Leia Como a Dificuldade do Sudoku É Classificada para entender o lado humano da análise computacional.