Nesta página
O Sudoku usa dígitos, mas não é um exercício de aritmética.
Sua matemática vem da estrutura das restrições: onde símbolos podem aparecer, quais combinações são compatíveis e quantas configurações satisfazem todas as condições ao mesmo tempo.
- linhas: 1–9 uma vez cada
- colunas: 1–9 uma vez cada
- sem regra de blocos
- linhas: 1–9 uma vez cada
- colunas: 1–9 uma vez cada
- blocos: 1–9 uma vez cada
Por que os números do Sudoku são realmente símbolos
No Sudoku clássico, o significado quantitativo de 1, 2, 3 e assim por diante não é usado.
Não somamos os dígitos, não multiplicamos valores e não comparamos magnitudes.
Poderíamos substituir 1–9 por nove letras ou nove ícones distintos, e a lógica básica permaneceria a mesma.
Os dígitos são convenientes porque são compactos e universalmente reconhecíveis.
Sudoku como quadrado latino com restrições
Um quadrado latino de ordem 9 usa nove símbolos de forma que cada símbolo apareça exatamente uma vez em cada linha e coluna.
Uma grade completa de Sudoku clássico satisfaz essas condições e adiciona as nove regiões 3×3.
Por isso:
Toda grade completa de Sudoku clássico é um quadrado latino com restrições extras de bloco.
Mas nem todo quadrado latino 9×9 satisfaz os blocos 3×3 do Sudoku.
Sudoku como problema de satisfação de restrições
Em um Constraint Satisfaction Problem (CSP), temos:
- variáveis;
- domínios de valores possíveis;
- restrições sobre quais combinações são permitidas.
No Sudoku:
- cada célula pode ser tratada como variável;
- seu domínio inicial é um subconjunto de 1–9;
- linhas, colunas e blocos impõem restrições de diferença.
Pistas reduzem domínios imediatamente. Deduções reduzem esses domínios durante a resolução.
Uma vantagem dessa visão é aproximar o raciocínio humano de técnicas computacionais sem dizer que são idênticos. Quando um jogador elimina um candidato, está reduzindo um domínio. Quando um programa faz constraint propagation, também reduz domínios — apenas com outra representação e outra política de escolha.
Restrições locais criam estrutura global
Cada regra parece local: uma célula não pode repetir um dígito na mesma linha, coluna ou bloco.
Mas essas restrições se sobrepõem.
Uma colocação em uma célula altera candidatos em vários peers. Essas mudanças podem criar Singles, Locked Candidates, subsets, Fish ou cadeias em áreas distantes.
A dificuldade e a riqueza do Sudoku surgem justamente dessa propagação global produzida por restrições locais simples.
Esse efeito explica por que uma dedução aparentemente pequena pode desbloquear uma região distante. A rede de restrições faz com que o valor informacional de um movimento não esteja limitado à house em que ele foi encontrado.
Sudoku como problema de cobertura exata
O Sudoku clássico também pode ser formulado como exact cover.
Existem 729 atribuições possíveis célula-dígito antes de considerar pistas: 81 células × 9 dígitos.
Cada atribuição precisa satisfazer quatro tipos de condição:
- cada célula recebe exatamente um dígito;
- cada dígito aparece exatamente uma vez em cada linha;
- cada dígito aparece exatamente uma vez em cada coluna;
- cada dígito aparece exatamente uma vez em cada bloco.
Isso produz 324 restrições no modelo clássico.
Algorithm X, frequentemente implementado com Dancing Links (DLX), é uma maneira eficiente de buscar uma cobertura exata dessas restrições.
As pistas iniciais simplesmente removem da matriz as atribuições incompatíveis e preenchem antecipadamente algumas condições. Depois, a busca escolhe linhas da matriz até que todas as 324 condições sejam cobertas exatamente uma vez.
Sudoku como problema semelhante a um grafo
Outra visão representa relações de incompatibilidade ou implicação como conexões.
Por exemplo:
- células que se enxergam possuem restrições compartilhadas;
- candidatos do mesmo dígito em uma house podem formar pares conjugados;
- Strong Links e Weak Links podem ser vistos como relações em uma rede;
- Coloring e Chains exploram caminhos nessa rede lógica.
A linguagem de grafos não é obrigatória para resolver Sudoku, mas ajuda a explicar por que técnicas aparentemente diferentes compartilham estruturas semelhantes.
Busca e backtracking
Um solver completo pode escolher uma possibilidade, propagar as consequências e voltar atrás quando encontra contradição.
Esse processo é backtracking.
Uma implementação eficiente costuma escolher primeiro uma célula ou variável muito restrita, reduzindo o branching factor.
Backtracking é particularmente útil para:
- encontrar uma solução completa;
- provar que não existe solução;
- contar soluções;
- verificar unicidade.
Ele não é necessariamente uma descrição de como um jogador humano resolve o puzzle.
Essa distinção explica por que um solver pode encontrar a resposta em milissegundos sem produzir uma explicação útil para um jogador. Eficiência computacional e qualidade pedagógica são objetivos diferentes.
Exact cover e backtracking não são opostos
Exact cover é uma representação do problema. Backtracking é uma estratégia de busca.
Algorithm X, por exemplo, realiza uma busca sistemática sobre uma representação de exact cover.
Portanto, não faz sentido tratar “exact cover” e “backtracking” como dois métodos mutuamente exclusivos no mesmo nível conceitual.
Complexidade computacional do Sudoku generalizado
Quando generalizamos o Sudoku para grades de tamanho crescente, o problema de decidir se existe solução é NP-completo.
Essa afirmação é sobre a família generalizada de problemas, em que o tamanho da grade faz parte da entrada.
Não significa que um Sudoku clássico 9×9 seja impraticável para computadores modernos.
O tamanho 9×9 é fixo e solvers completos eficientes resolvem ou verificam instâncias com extrema rapidez.
Quantas grades completas de Sudoku clássico existem?
O número de grades completas válidas de Sudoku clássico 9×9 é:
6.670.903.752.021.072.936.960.
mais de seis sextilhões de grades clássicas completas de Sudoku
Esse número conta grades com valores diferentes como diferentes, mesmo que estejam relacionadas por transformações que preservam a estrutura do Sudoku.
Grades de Sudoku essencialmente diferentes
Se agrupamos grades relacionadas por simetrias e relabeling de dígitos, o número cai drasticamente.
Existem aproximadamente 5,47 bilhões de grades solução essencialmente diferentes sob uma definição comum de equivalência do Sudoku.
A palavra “essencialmente” é importante: estamos escolhendo não distinguir grades que podem ser transformadas umas nas outras por operações estruturais válidas.
Essa redução mostra como simetria e equivalência transformam um espaço de contagem gigantesco em classes estruturais. Em geração e pesquisa, isso evita tratar como matematicamente novos casos que diferem apenas por uma transformação que preserva o Sudoku.
Por que a contagem de grades solução não é o número de quebra-cabeças Sudoku
Uma grade completa só descreve a solução final.
Um puzzle adiciona outra camada: quais células são reveladas como pistas.
A mesma grade solução pode sustentar inúmeros conjuntos de pistas, e muitos desses conjuntos não serão únicos ou não oferecerão um bom caminho de resolução.
Portanto, contar solution grids e contar puzzles são problemas diferentes.
Simetria na matemática do Sudoku
A palavra simetria aparece em mais de um sentido.
Equivalência de grades solução
Podemos aplicar transformações que preservam a validade, como:
- permutar os dígitos 1–9;
- trocar linhas dentro da mesma banda;
- trocar colunas dentro da mesma pilha;
- trocar bandas inteiras;
- trocar pilhas inteiras;
- transpor a grade;
- aplicar certas reflexões/rotações equivalentes.
Essas operações ajudam a estudar classes de equivalência.
Simetria da disposição das pistas
Construtores frequentemente usam clue patterns com simetria visual, como rotação de 180°.
Isso é uma escolha editorial/estética. Não é uma regra necessária do Sudoku clássico.
Permutações ajudam a explicar equivalência no Sudoku
Se renomeamos consistentemente os dígitos de uma grade válida — por exemplo, trocando todos os 1 por 7 e todos os 7 por 1 — a grade continua válida.
O mesmo vale para certas permutações de linhas, colunas, bandas e pilhas.
Essas simetrias reduzem o espaço que precisa ser tratado como estruturalmente distinto em provas e enumerações.
Combinatória da seleção de pistas
Dada uma grade solução, existem muitas maneiras de escolher subconjuntos de células como pistas.
Mas quase todos os subconjuntos são inadequados para um objetivo específico.
Alguns:
- não têm solução única;
- são inconsistentes se não vierem de uma grade válida;
- são fáceis demais ou difíceis demais;
- contêm pistas redundantes;
- não apresentam o caminho lógico desejado.
A construção combina combinatória com verificação e análise.
Mesmo fixando um número de pistas, como 25 ou 30, o número bruto de subconjuntos possíveis é enorme. A maior parte não produz um puzzle editorialmente útil. Esse contraste mostra por que “muitas combinações” não equivale a “muitos bons Sudokus”: unicidade, dificuldade e qualidade filtram quase todo o espaço.
Mínimo de pistas como problema extremo
Perguntar pelo menor número possível de pistas é um problema extremal.
No Sudoku clássico 9×9 único, o limite é 17.
A prova de que 16 é impossível depende de reduzir o espaço de busca e cobrir sistematicamente estruturas relevantes.
Dificuldade como modelo de computação humana
A dificuldade para um humano não é determinada simplesmente pela quantidade de soluções — um puzzle publicado normalmente tem uma — nem pela quantidade de pistas.
Ela depende do trabalho necessário dentro de um modelo de resolução humana:
- quais técnicas são necessárias;
- quantas deduções precisam ser encadeadas;
- quão difícil é reconhecer o próximo padrão;
- quantos caminhos produtivos existem.
Por que diferentes solvers de Sudoku têm funções diferentes
Um único algoritmo não precisa desempenhar todos os papéis.
Solver completo / contador de soluções
Prioriza correção e completude. Deve encontrar soluções ou provar quantas existem.
Solver de estilo humano
Prioriza deduções explicáveis usando técnicas que um jogador pode aprender.
Analisador de dificuldade
Interpreta o solve path, técnicas, dependências e outros sinais para produzir uma pontuação ou categoria.
Gerador
Cria ou escolhe solution grids e clue sets, verifica unicidade e aplica requisitos de dificuldade/qualidade.
FAQ
Sudoku é baseado em aritmética?
Não. Os dígitos funcionam como símbolos, não como quantidades que precisam ser calculadas.
Toda grade completa de Sudoku é um quadrado latino?
Sim, porque cada dígito aparece uma vez por linha e coluna.
Todo quadrado latino 9×9 é uma grade válida de Sudoku?
Não. Ele também precisa satisfazer os nove blocos 3×3.
Quantas grades completas de Sudoku clássico existem?
6.670.903.752.021.072.936.960.
Quantas grades completas essencialmente diferentes existem?
Aproximadamente 5,47 bilhões sob a equivalência padrão usada na enumeração do Sudoku.
Por que existem tantas grades se as regras são tão simples?
Porque restrições simples ainda permitem uma quantidade enorme de combinações globais compatíveis.
Sudoku é NP-completo?
O Sudoku generalizado é NP-completo. Essa afirmação não significa que instâncias clássicas 9×9 sejam difíceis para computadores modernos.
Algorithm X é uma técnica humana de Sudoku?
Normalmente não. É um algoritmo de busca para problemas de exact cover, muito útil em solvers computacionais.
A enorme contagem de grades solução determina a dificuldade do Sudoku?
Não. A dificuldade humana depende do caminho lógico de um puzzle específico.
O que aprender depois
Leia Teoria do Sudoku para o panorama geral, Como Sudokus São Gerados para construção e Como a Dificuldade do Sudoku É Classificada para o modelo humano de rating.