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

A matemática do Sudoku

Atualizado em 2026-10-05

Um quadrado latino com blocos

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

Fontes: Wikipedia: Latin square

Quantas grades existem

Bertram Felgenhauer e Frazer Jarvis contaram as grades 9×9 preenchidas em 2005: existem 6.670.903.752.021.072.936.960, cerca de 6,67 × 10²¹. Muitas delas são a mesma grade sob outra aparência. Conte duas grades como uma só quando for possível transformar uma na outra trocando os algarismos, girando ou refletindo a grade, ou reordenando linhas e colunas de maneiras que mantenham a grade válida, e restam 5.472.730.538 grades 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 9×9 com 16 pistas ou menos tem exatamente uma solução. Gary McGuire, Bastian Tugemann e Gilles Civario demonstraram isso com uma busca exaustiva por computador e anunciaram o resultado em janeiro de 2012. Dezessete é o mínimo, não uma garantia: muitas grades com 17 pistas ainda têm mais de uma solução.

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

Sudoku como coloração de grafos

Desenhe um ponto para cada uma das 81 células e conecte dois pontos sempre que suas células compartilharem uma linha, uma coluna ou um bloco. Esse grafo do Sudoku tem 810 conexões, e cada ponto tem exatamente 20 vizinhos. Resolver o jogo significa estender as cores fixadas pelas pistas de modo que pontos conectados 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 conectados entre si, e qualquer grade preenchida mostra que nove são suficientes.

Fontes: Wikipedia: Sudoku graph

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

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

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

Veja também

Fontes

Todos os artigos →