A matemática do Sudoku
Um tabuleiro de Sudoku é um pequeno objeto matemático, e muita coisa já foi demonstrada sobre ele. Aqui estão os principais resultados, do mais simples ao mais profundo, cada um com sua demonstração: completa quando cabe em poucas linhas, a ideia dela quando foi preciso um longo artigo ou um computador.
Equivalência direta
O Sudoku é um problema de coloração de grafos
Teorema. Resolver um Sudoku é colorir com 9 cores um grafo de 81 vértices, respeitando as cores que os números dados impõem. Cada vértice tem exatamente 20 vizinhos.
Tomemos um vértice por casa e liguemos dois vértices quando suas casas compartilham uma linha, uma coluna ou um bloco. Os nove números viram nove cores, e colorir o grafo é dar uma cor a cada vértice sem que dois vizinhos tenham a mesma.
Demonstração
De uma solução a uma coloração: demos a cada vértice a cor do número da sua casa. Duas casas vizinhas compartilham uma linha, uma coluna ou um bloco, então têm números diferentes, e seus vértices recebem cores diferentes.
De uma coloração a uma solução: as nove casas de uma linha são todas vizinhas entre si, então precisam de nove cores diferentes. Como só há nove, cada uma aparece exatamente uma vez na linha. O mesmo vale para cada coluna e cada bloco: lendo as cores de volta como números, obtém-se uma solução.
A conta das vizinhas
Uma casa tem outras 8 na sua linha, 8 na sua coluna e 8 no seu bloco. Mas 2 casas do seu bloco estão também na sua linha, e 2 na sua coluna: foram contadas duas vezes.
8 + 8 + 8 − 2 − 2 = 20
O grafo tem, portanto, 81 × 20 ÷ 2 = 810 arestas, cada uma contada a partir das duas pontas. E como uma linha precisa de nove cores e nove bastam, o grafo precisa de exatamente nove: seu número cromático é 9.
No My Sudoku
Visto assim, um Single nu é um vértice cujos 20 vizinhos já usam 8 das 9 cores: só lhe resta uma.
Fonte: Wikipédia: Mathematics of Sudoku.
Codificação lógica
O Sudoku é um problema de cobertura exata
Teorema. Uma solução de Sudoku é uma escolha de 81 linhas, entre as 729 de uma matriz de zeros e uns com 324 colunas, que cobre cada coluna exatamente uma vez.
Cada jogada no Sudoku coloca um número d numa casa (l, c), e cada colocação satisfaz quatro restrições ao mesmo tempo:
- casa: a casa (l, c) tem um número;
- linha: o número d está na linha l;
- coluna: o número d está na coluna c;
- bloco: o número d está no bloco de (l, c).
Cada tipo aparece 81 vezes: 81 casas, e 9 números para cada uma das 9 linhas, das 9 colunas e dos 9 blocos.
4 × 81 = 324 restrições · 81 × 9 = 729 colocações
Escrevamos uma matriz com uma linha por colocação e uma coluna por restrição, com um 1 onde a colocação satisfaz a restrição. Cada linha tem exatamente quatro uns. Colocar um 7 em L2C5, por exemplo, cobre quatro colunas:
- casa L2C5
- um 7 na linha 2
- um 7 na coluna 5
- um 7 no bloco 2
Demonstração
Uma cobertura exata escolhe linhas da matriz de modo que cada coluna tenha exatamente um 1 entre elas. As 81 restrições de casa dão a cada casa exatamente um número; as de linha, coluna e bloco põem cada número exatamente uma vez em cada linha, coluna e bloco. Isso é uma solução do Sudoku e, inversamente, as 81 colocações de uma solução satisfazem cada restrição uma vez. Os números dados são linhas escolhidas de antemão.
cobertura exata ⟺ solução: 81 linhas de 729
No My Sudoku
Muitos programas de resolução trabalham com essa forma, entre eles o algoritmo X de Donald Knuth e seus Dancing Links ("links dançantes"): eles sempre exploram primeiro a restrição com menos opções. A busca do My Sudoku faz o mesmo com as restrições de casa: tenta primeiro a casa com menos números possíveis.
A matriz mostra também que os dois singles são uma só ideia: um Single nu é uma restrição de casa, e um Single oculto, uma de linha, coluna ou bloco, à qual só resta uma colocação. Nos dois casos, uma coluna com um único 1.
Fontes: Donald E. Knuth, Dancing Links (2000), Wikipédia: Mathematics of Sudoku.
Contagem por computador, com as simetrias
Existem 6.670.903.752.021.072.936.960 tabuleiros
Teorema. Há exatamente 6.670.903.752.021.072.936.960 maneiras de preencher um tabuleiro de 9 × 9 seguindo as regras, cerca de 6,67 × 10²¹. Deixando as simetrias de lado, 5.472.730.538 delas são essencialmente diferentes.
Bertram Felgenhauer e Frazer Jarvis os contaram em 2005; Ed Russell e Frazer Jarvis contaram pouco depois os essencialmente diferentes.
Por que não (9!)⁹?
Cada linha pode ser ordenada de 9! = 362.880 maneiras, então se poderia esperar (9!)⁹ tabuleiros, cerca de 1,1 × 10⁵⁰. Mas esse número conta quaisquer nove linhas empilhadas, com números repetidos em colunas e blocos: as restrições não são independentes, e o número real é muito menor.
Uma parte verificável: um múltiplo de 9!
Renomeemos os números de um tabuleiro: todo 1 vira 5, todo 5 vira 2, e assim por diante, segundo uma das 9! maneiras de permutar os nove números. Cada linha, coluna e bloco continua tendo cada número uma vez: o resultado também é um tabuleiro. Duas renomeações diferentes de um tabuleiro dão dois tabuleiros diferentes, e renomear um tabuleiro renomeado dá outro da mesma família. Os tabuleiros se dividem, portanto, em famílias de exatamente 9! tabuleiros, e seu número é um múltiplo de 9!:
6.670.903.752.021.072.936.960 = 9! × 18.383.222.420.692.992
Como a contagem foi feita
Felgenhauer e Jarvis fixaram o primeiro bloco como 1 a 9 na ordem de leitura, o que responde pelo 9!, e contaram as maneiras de completar as três primeiras linhas: 2.612.736, ou seja, 56 × 6⁶. Muitas se parecem, já que uma vira outra quando se trocam colunas ou se renomeiam números, e podem ser completadas de tantas maneiras quanto ela; agrupando-as, fizeram um computador contar, para cada grupo, as maneiras de preencher as seis últimas linhas. O total se decompõe assim, e seu último fator é um número primo:
9! × 72² × 2⁷ × 27.704.267.971
Os tabuleiros essencialmente diferentes
Refletir um tabuleiro na sua diagonal, trocar duas faixas ou duas pilhas de blocos, duas linhas de uma mesma faixa ou duas colunas de uma mesma pilha, ou renomear seus números dá um tabuleiro que, no fundo, é o mesmo. Essas operações formam um grupo de 9! × 3.359.232 elementos. Dividir a contagem por esse número dá cerca de 5.472.448.000: perto, mas errado. Alguns tabuleiros são simétricos e ficam iguais com alguma operação, então sua família é menor que o grupo e a divisão os conta de menos. O lema de Burnside, que conta os tabuleiros que cada operação deixa iguais, corrige a conta:
5.472.730.538 tabuleiros essencialmente diferentes
A mesma conta à mão, em 4 × 4
| 1 | 2 | 3 | 4 |
| 3 | 4 | 1 | 2 |
| 2 | 1 | 4 | 3 |
| 4 | 3 | 2 | 1 |
Com quatro números e blocos de 2 × 2, toda a conta cabe em poucas linhas. Preenchamos o primeiro bloco: 4! = 24 maneiras e, renomeando os números, podemos supor que ele é 1 2 / 3 4. O resto da linha 1 tem então 3 e 4, e o resto da linha 2, 1 e 2, numa ordem ou noutra: 4 maneiras. O mesmo vale para o resto das colunas 1 e 2: 4 maneiras. Dessas 16 combinações, 12 deixam exatamente uma maneira de preencher o último bloco, e 4 não deixam nenhuma:
24 × 12 = 288 tabuleiros
Entre os quadrados latinos
Um tabuleiro é um quadrado latino de ordem 9, cada número uma vez por linha e por coluna, com a regra dos blocos a mais. Há 5.524.751.496.156.892.842.531.225.600 quadrados latinos de ordem 9: os blocos só deixam cerca de um em cada 828.000.
Fontes: Frazer Jarvis, Sudoku enumeration problems, OEIS A002860, Wikipédia: Mathematics of Sudoku.
Demonstração em poucas linhas
Os números dados mostram pelo menos oito algarismos diferentes
Teorema. Num Sudoku com solução única, pelo menos oito dos nove algarismos aparecem entre os números dados.
Oito algarismos diferentes, e não oito números dados.
Demonstração
Suponhamos que dois algarismos, por exemplo o 4 e o 7, não apareçam entre os números dados. Tomemos uma solução e troquemos nela, em toda parte, os 4 pelos 7 e os 7 pelos 4.
Cada linha tinha um 4 e um 7, e continua tendo: eles só trocaram de lugar. O mesmo vale para cada coluna e cada bloco, então o novo tabuleiro também é uma solução. Ele difere do primeiro onde havia um 4 ou um 7, e respeita todos os números dados, já que nenhum é 4 nem 7. O Sudoku teria duas soluções. Então pode faltar no máximo um algarismo entre os números dados.
Bem no limite
O Sudoku de 17 números dados mais abaixo está bem no limite: seus números dados mostram oito algarismos, sem nenhum 6.
Num tabuleiro de N × N, o mesmo raciocínio exige N − 1 símbolos diferentes entre os números dados.
Fonte: Wikipédia: Mathematics of Sudoku.
Demonstração por construção
Quatro casas podem bastar para estragar um Sudoku
Teorema. Se quatro casas nos cantos de um retângulo, em duas linhas, duas colunas e dois blocos, têm a b / b a numa solução e nenhuma delas é um número dado, o Sudoku tem uma segunda solução.
Demonstração
| a | b |
| b | a |
| b | a |
| a | b |
Troquemos a e b nas quatro casas. Cada uma das duas linhas continua tendo um a e um b, e cada uma das duas colunas também. As quatro casas ficam duas a duas em dois blocos, e cada par tem um a e um b: depois da troca, os blocos continuam certos. Nada mais muda: o novo tabuleiro também é uma solução e respeita todos os números dados, já que nenhuma das quatro casas é um deles.
Os conjuntos inevitáveis
Um conjunto de casas assim, das quais pelo menos uma precisa ser um número dado, se chama conjunto inevitável. Aqui, um Sudoku com 77 números dados, só quatro casas vazias, tem duas soluções: a quantidade de números dados diz pouco; o lugar deles, muito.
Nunca menos de quatro casas
Inversamente, duas soluções diferentes de um mesmo Sudoku sempre diferem em pelo menos quatro casas. Então um Sudoku com 78 números dados ou mais nunca tem duas soluções, e o retângulo é a menor ambiguidade que existe.
Olhemos as casas em que as duas soluções diferem. Uma linha não pode conter só uma delas: suas outras oito casas teriam os mesmos oito algarismos nas duas soluções, e sobraria o mesmo nono algarismo para a última. Então uma linha, ou uma coluna, que contém uma dessas casas contém pelo menos duas. Tomemos uma, x. Sua linha contém outra, y; sua coluna, outra, z; e a linha de z, outra, w. Essa casa w não é x, que não está na linha de z, nem y, que está na linha de x. São quatro casas diferentes.
No My Sudoku
A técnica do Retângulo único inverte isso: como um Sudoku bem feito só tem uma solução, esse retângulo nunca pode se formar, e os candidatos que o formariam podem ser eliminados.
Fonte: Wikipédia: Mathematics of Sudoku.
Demonstração exaustiva por computador
Um Sudoku precisa de pelo menos 17 números dados
Teorema. Um Sudoku de 9 × 9 com solução única tem pelo menos 17 números dados. Existem alguns com 17; nenhum com 16.
Gary McGuire, Bastian Tugemann e Gilles Civario o demonstraram em 2012, com uma busca exaustiva por computador. Conhecem-se dezenas de milhares de Sudokus com 17 números dados.
Ideia da demonstração
A demonstração se apoia nos conjuntos inevitáveis vistos acima: conjuntos de casas de um tabuleiro que os números dados precisam atingir, senão seus algarismos poderiam ser rearranjados numa segunda solução. Números dados que determinam um tabuleiro precisam atingir cada um dos seus conjuntos inevitáveis: formam um conjunto de acerto (hitting set) dessa família. A busca foi assim:
- para cada um dos 5.472.730.538 tabuleiros essencialmente diferentes, encontrar muitos dos seus conjuntos inevitáveis;
- listar todos os conjuntos de 16 casas que atingem todos eles, a parte difícil, para a qual os autores criaram um algoritmo novo;
- verificar se os algarismos do tabuleiro nessas 16 casas o determinam;
- isso nunca aconteceu.
É uma demonstração de verdade, mas que só um computador consegue fazer: ninguém conseguiria conferi-la à mão.
A mesma demonstração em miniatura
Nos tabuleiros de 4 × 4, a mesma busca é minúscula. Entre os 288 tabuleiros, nenhum é determinado por 3 das suas casas, enquanto alguns são por 4: o mínimo ali é 4, o que um computador confere num instante testando todos os casos.
Minimal não é mínimo
Um Sudoku é minimal quando tirar qualquer um dos seus números dados deixa passar uma segunda solução, e mínimo quando nenhum Sudoku tem menos: 17. Um Sudoku pode ser minimal com 25 números dados, sem que nenhum possa sair, enquanto outros se viram com menos.
Fora os do nível Muito fácil, os Sudokus do My Sudoku são minimais: ele preenche um tabuleiro ao acaso e depois tira os números um a um, em ordem aleatória, devolvendo qualquer um cuja retirada deixe passar uma segunda solução. Seus Sudokus costumam terminar com 22 a 27 números dados.
Fontes: Gary McGuire, Bastian Tugemann, Gilles Civario, There is no 16-Clue Sudoku (2012), Wikipédia: Mathematics of Sudoku.
Demonstração por redução
O Sudoku é NP-completo
Teorema. Decidir se um Sudoku parcialmente preenchido de n² × n² casas, com blocos de n × n, tem solução é um problema NP-completo.
Takayuki Yato e Takahiro Seta o demonstraram em 2003, partindo dos quadrados latinos. Um problema é NP-completo quando tem duas propriedades: está em NP, ou seja, uma solução proposta pode ser verificada rápido, e é NP-difícil, ou seja, todo problema de NP pode ser traduzido nele em tempo polinomial. A demonstração tem duas partes.
Parte A: o Sudoku está em NP
Tomemos um tabuleiro preenchido de lado N = n². Para verificá-lo, percorrem-se suas N linhas, N colunas e N blocos, e compara-se com os números dados. Verificar que uma linha tem uma vez cada símbolo de 1 a N leva cerca de N operações; as linhas levam então cerca de N × N, e o mesmo vale para as colunas e os blocos:
3 × N × O(N) = O(N²)
É um número de operações proporcional às N² casas do tabuleiro. Encontrar uma solução pode ser difícil; verificar uma é rápido.
Parte B: o Sudoku é NP-difícil
Um quadrado latino de ordem N preenche uma grade de N × N com N símbolos, cada um uma vez por linha e por coluna: as regras do Sudoku, sem os blocos.
| 1 | 2 | 3 |
| 2 | 3 | 1 |
| 3 | 1 | 2 |
Charles Colbourn demonstrou em 1984 que decidir se um quadrado latino parcialmente preenchido pode ser completado é NP-completo. Yato e Seta transformam qualquer quadrado latino parcialmente preenchido L num Sudoku parcialmente preenchido S(L), em tempo polinomial: os números dados de S(L) são dispostos de modo que suas casas livres só possam ser preenchidas como L pode ser completado. Cada maneira de completar L dá exatamente uma solução de S(L), e vice-versa (uma redução parcimoniosa):
L pode ser completado ⟺ S(L) tem solução
Um método rápido para o Sudoku daria, portanto, um método rápido para os quadrados latinos. Como completar um quadrado latino é NP-completo, o Sudoku é NP-difícil; com a parte A, é NP-completo.
O que isso não quer dizer
Não quer dizer que os Sudokus de 9 × 9 sejam difíceis: seu tamanho é fixo, e um computador resolve qualquer um num instante. A NP-completude diz respeito à família inteira, à medida que n cresce: não se conhece nenhum método que resolva cada tabuleiro num tempo polinomial no seu tamanho, e encontrar um provaria que P = NP, uma das grandes questões em aberto da matemática, com um prêmio de um milhão de dólares do Instituto Clay.
Uma segunda solução: ASP-completo
Yato e Seta demonstram mais: dado um Sudoku e uma das suas soluções, decidir se ele tem outra é igualmente difícil. O problema é ASP-completo (do inglês Another Solution Problem, "problema de outra solução"). É a pergunta que todo criador de Sudokus enfrenta, já que um Sudoku bem feito tem uma única solução.
Por isso o gerador do My Sudoku não deixa nada ao acaso: depois de cada número que tira, uma busca procura uma segunda solução, parando na primeira que encontra, e se encontrar uma, o número volta para o lugar.
Fontes: Takayuki Yato, Takahiro Seta, Complexity and Completeness of Finding Another Solution and Its Application to Puzzles, IEICE Transactions on Fundamentals E86-A (2003), Charles J. Colbourn, The complexity of completing partial Latin squares (1984), Wikipédia: Mathematics of Sudoku.
Em resumo
| Resultado | Tipo de demonstração |
|---|---|
| O Sudoku é um problema de coloração de grafos | Equivalência direta |
| O Sudoku é um problema de cobertura exata | Codificação lógica |
| Existem 6.670.903.752.021.072.936.960 tabuleiros | Contagem por computador, com as simetrias |
| Os números dados mostram pelo menos oito algarismos diferentes | Demonstração em poucas linhas |
| Quatro casas podem bastar para estragar um Sudoku | Demonstração por construção |
| Um Sudoku precisa de pelo menos 17 números dados | Demonstração exaustiva por computador |
| O Sudoku é NP-completo | Demonstração por redução |