Sudoku O Sudoku parece um jogo de números, mas os dígitos não funcionam como quantidades. No Sudoku clássico, 8 não é maior do que 3 para as regras: são apenas símbolos diferentes.
A verdadeira matemática está nas restrições que se sobrepõem. Cada casa pertence a uma linha, uma coluna e um bloco. Resolver é provar que colocações ainda são possíveis.
A matemática do Sudoku é sobretudo combinatória, lógica e satisfação de restrições. Uma grelha 9x9 pede que coloque os dígitos 1 a 9 para que cada linha, coluna e bloco 3x3 contenha cada dígito exatamente uma vez.
O Sudoku é mesmo matemático?
Sim, mas não por usar dígitos. Os dígitos são etiquetas e podiam ser letras, cores ou símbolos.
O Sudoku clássico é um problema de lógica: respeitar restrições e deduzir que valores são forçados.
A matemática do Sudoku envolve permutações, restrições, simetrias, prova e unicidade.
Estrutura da grelha 9x9
Uma grelha padrão tem 81 casas: 9 linhas e 9 colunas, divididas em nove blocos 3x3.
Há 27 casas/grupos: 9 linhas, 9 colunas e 9 blocos. Cada grupo deve conter os dígitos 1 a 9 exatamente uma vez.
Cada casa pertence a três grupos. Essa sobreposição dá força lógica ao puzzle.
Sudoku em números
| Tema | Número ou ideia | Significado |
|---|---|---|
| Tamanho | 9x9 | 81 casas |
| Símbolos | Dígitos 1-9 | Etiquetas, não quantidades |
| Grupos | Linhas, colunas, blocos | 27 no total |
| Regra | Cada dígito uma vez | Em cada grupo |
| Modelo | Satisfação de restrições | Também exact cover |
| Grelhas completas | 6,670,903,752,021,072,936,960 | Soluções 9x9 válidas |
| Grelhas essenciais | 5,472,730,538 | Depois das simetrias |
| Mínimo de pistas | 17 | Para solução única |
O sistema de restrições
Uma solução cumpre quatro requisitos: um dígito por casa, cada dígito uma vez por linha, uma vez por coluna e uma vez por bloco.
Formalmente, o Sudoku pode ser modelado com 324 restrições exatas: 81 de casa, 81 linha-dígito, 81 coluna-dígito e 81 bloco-dígito.
Um candidato como linha 4, coluna 7, dígito 9 satisfaz quatro restrições ao mesmo tempo.
Quantas grelhas são possíveis?
Existem 6,670,903,752,021,072,936,960 soluções completas de Sudoku 9x9.
Se forem descontadas simetrias como rotações, reflexos, troca de dígitos e trocas compatíveis de linhas ou colunas, restam 5,472,730,538 grelhas essencialmente diferentes.
O espaço de soluções é enorme, mas as regras são fortes o bastante para criar puzzles com uma só resposta.
Pistas, unicidade e dificuldade
Um puzzle começa com pistas. A função matemática delas é reduzir todas as soluções possíveis a exatamente uma.
Um bom puzzle não é apenas uma grelha com números removidos. As pistas devem preservar a unicidade e criar um caminho lógico interessante.
O mínimo para um Sudoku clássico válido é 17 pistas. Dezasseis pistas não bastam.
A lógica da resolução
As técnicas humanas são pequenas provas. Um naked single prova que uma casa tem apenas um candidato. Um hidden single prova que um dígito tem apenas um lugar num grupo.
Pares, triplos, candidatos bloqueados, peixes, asas e cadeias são formas mais avançadas da mesma ideia: eliminar o que contradiz as restrições.
Para usar isto na prática, veja também o guia de técnicas de Sudoku.
Sudoku como problema exact cover
Um computador pode transformar Sudoku num problema exact cover: escolher colocações que cubram cada restrição exatamente uma vez.
Algorithm X e dancing links de Donald Knuth são um método famoso; backtracking com propagação de restrições também é comum.
O 9x9 comum resolve-se muito depressa por computador, mas Sudoku generalizado em grelhas maiores é NP-completo.
Simetrias e transformações
Pode trocar linhas dentro da mesma banda, colunas dentro da mesma pilha, bandas inteiras, rodar ou refletir a grelha, ou renomear dígitos.
Se todos os 1 passarem a 7 e todos os 7 passarem a 1, a solução continua válida.
Estas simetrias ajudam a contar grelhas e a criar padrões de pistas equilibrados.
Math Sudoku, Killer Sudoku e Calcudoku
A intenção de pesquisa importa. Matemática do Sudoku costuma significar a teoria do Sudoku clássico. Math Sudoku pode significar variantes com cálculo.
Para uma variante com somas, experimente Killer Sudoku. Para uma variante mais aritmética, experimente Calcudoku.
No Sudoku clássico, a matemática está nas restrições. Nessas variantes, o cálculo passa a fazer parte visível das regras.
O Sudoku é matemático porque pede provas do que é forçado, não porque pede cálculos.
Essa é a elegância do Sudoku: nove símbolos simples, uma grelha pequena e estrutura suficiente para muita lógica.
Perguntas frequentes
Usa combinatória, lógica, satisfação de restrições, ideias de coloração de grafos, exact cover e simetrias.
Não. No Sudoku clássico os dígitos são símbolos, não quantidades.
Existem 6,670,903,752,021,072,936,960 soluções completas, ou 5,472,730,538 grelhas essencialmente diferentes depois das simetrias.
Para Sudoku clássico com solução única, o mínimo é 17 pistas.
Nem sempre. Math Sudoku costuma significar variantes aritméticas como Killer Sudoku ou Calcudoku.