Enciclopédia do Sudoku · Matemática e computação

A matemática do Sudoku

Atualizado em 2026-10-05

Um quadrado latino com blocos

Num quadrado latino, cada símbolo aparece uma vez em cada linha e em cada coluna. Um Sudoku concluído é um quadrado latino de tamanho 9 com uma condição a mais: cada um dos nove blocos 3×3 também contém cada algarismo uma vez.

Fontes: Wikipedia: Latin square

Quantas grelhas existem

Bertram Felgenhauer e Frazer Jarvis contaram as grelhas de 9×9 completas em 2005: são 6.670.903.752.021.072.936.960, cerca de 6,67 × 10²¹. Muitas delas são a mesma grelha disfarçada. Contando duas grelhas como uma só quando é possível transformar uma na outra trocando os algarismos entre si, rodando-a ou refletindo-a, ou reordenando linhas e colunas das formas que mantêm a grelha válida, restam 5.472.730.538 grelhas essencialmente diferentes, um número calculado por Ed Russell e Frazer Jarvis.

Fontes: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

O mínimo de 17 pistas

Nenhum Sudoku padrão de 9×9 com 16 pistas ou menos tem exatamente uma solução. Gary McGuire, Bastian Tugemann e Gilles Civario demonstraram-no com uma pesquisa exaustiva em computador e anunciaram o resultado em janeiro de 2012. Dezassete é o mínimo, não uma garantia: muitas grelhas com 17 pistas continuam a ter mais de uma solução.

Fontes: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

O Sudoku como coloração de grafos

Desenhe um ponto por cada uma das 81 células e ligue dois pontos sempre que as respetivas células partilhem uma linha, uma coluna ou um bloco. Este grafo do Sudoku tem 810 ligações, e cada ponto tem exatamente 20 vizinhos. Resolver o passatempo significa estender as cores fixadas pelas pistas de modo que pontos ligados nunca tenham a mesma cor. São necessárias pelo menos nove cores, porque cada linha, coluna e bloco é um grupo de nove pontos todos ligados entre si, e qualquer grelha completa mostra que nove bastam.

Fontes: Wikipedia: Sudoku graph

Difícil em geral, rápido em 9×9

Para grelhas de Sudoku que podem crescer sem limite (n²×n² com blocos n×n), decidir se uma grelha parcialmente preenchida pode ser completada é um problema NP-completo, resultado que Takayuki Yato e Takahiro Seta publicaram em 2003. Programas de computador eficientes resolvem normalmente passatempos comuns de 9×9 numa fração de segundo, embora o tempo dependa do programa, do computador e do passatempo.

Fontes: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

Ver também

Fontes

Todos os artigos →