Para um Sudoku padrão 9×9 que precisa ter exatamente uma solução, o número mínimo comprovado de pistas iniciais é:
17
Existem Sudokus únicos com 17 pistas.
Não existe Sudoku clássico único com 16 pistas.
Essa segunda afirmação foi estabelecida por uma busca computacional exaustiva de Gary McGuire, Bastian Tugemann e Gilles Civario.
O resultado responde a uma pergunta matemática muito específica. Ele não significa que 17 pistas produzam os melhores Sudokus, os mais difíceis ou aqueles que um gerador deveria preferir criar.
O que conta como pista?
Uma pista é um dígito presente antes de o jogador começar.
Também pode ser chamada given ou número inicial.
Um Sudoku com 17 pistas começa com:
- 17 células preenchidas;
- 64 células vazias.
A solução completa continua contendo 81 dígitos.
O número de pistas descreve o estado inicial, não o tamanho da solução.
Por que a unicidade faz parte da pergunta
Se a unicidade não importasse, poderíamos remover muitas pistas e deixar um estado inicial com uma enorme quantidade de conclusões possíveis.
Isso não responderia ao problema clássico do número mínimo de pistas.
A pergunta real é:
Qual é o menor conjunto de pistas que ainda determina uma, e somente uma, grade clássica 9×9 completa e válida?
Isso combina dois requisitos:
- as pistas iniciais são compatíveis com uma solução;
- não existe uma segunda solução.
Por que 17 não era uma resposta óbvia
Pesquisadores e colecionadores de quebra-cabeças já haviam encontrado Sudokus únicos válidos com 17 pistas.
Durante muito tempo, ninguém encontrou um exemplo com 16.
Mas:
“Ninguém encontrou um”
não é o mesmo que:
“Nenhum existe.”
O desafio era provar que um Sudoku de 16 pistas ainda desconhecido não estava escondido em algum ponto do enorme espaço de busca do Sudoku.
O resultado que elimina 16 pistas
McGuire, Tugemann e Civario transformaram o problema em uma busca computacional exaustiva envolvendo unavoidable sets e hitting sets.
Em alto nível:
- comece com grades solução completas de Sudoku;
- identifique estruturas que um conjunto de pistas precisa intersectar para que o quebra-cabeça continue único;
- trate as posições candidatas a pistas como um problema de hitting set;
- enumere eficientemente os pequenos hitting sets possíveis;
- teste exaustivamente as possibilidades com 16 pistas;
- não encontre nenhum Sudoku único com 16 pistas.
Isso estabelece o limite inferior:
Todo Sudoku clássico 9×9 com solução única precisa de pelo menos 17 pistas.
A prova é computacional.
Não é uma demonstração curta baseada simplesmente na contagem de células ou unidades.
O que é um unavoidable set?
Para uma determinada grade solução, um unavoidable set é um conjunto de células com a propriedade de que um Sudoku único baseado naquela solução precisa conter pelo menos uma pista desse conjunto.
Por quê?
Porque, se todas essas células ficassem sem pistas, uma conclusão alternativa poderia sobreviver.
Um conjunto válido de pistas precisa, portanto, “atingir” cada unavoidable set relevante.
É daí que surge a formulação por hitting sets.
Para uma página pública, essa intuição é suficiente; o artigo científico contém os detalhes computacionais.
Minimum vs minimal
A distinção importa.
Sudoku de número mínimo de pistas
Usa o menor número global possível de pistas.
Para Sudoku clássico 9×9 com solução única:
17 pistas.
Sudoku minimal
Cada pista individual é necessária naquele quebra-cabeça específico.
Se qualquer pista for removida, a unicidade é perdida.
Um Sudoku minimal pode ter:
- 18 pistas;
- 24 pistas;
- mais.
“Minimal” não significa “tem 17”.
Significa:
Nenhuma pista é redundante para preservar a unicidade.
Todo Sudoku de 17 pistas é automaticamente minimal?
Um Sudoku único com 17 pistas não pode perder uma pista e continuar sendo um Sudoku clássico único, porque isso produziria um Sudoku único com 16 pistas — algo que o resultado mínimo descarta.
Portanto, todo Sudoku válido e único com 17 pistas é necessariamente minimal.
O contrário é falso:
Um Sudoku minimal não precisa ter 17 pistas.
Posso escolher quaisquer 17 células de uma grade solução?
Não.
A maioria dos conjuntos arbitrários de 17 células não produzirá um bom Sudoku único.
Eles podem:
- permitir várias soluções;
- não ter solução se os dígitos iniciais não forem escolhidos de forma consistente;
- falhar no modelo de resolução humana pretendido;
- produzir uma dificuldade indesejada ou incompatível.
O limite inferior global diz que alguns Sudokus únicos com 17 pistas existem.
Ele não diz que 17 pistas sejam suficientes em posições arbitrárias.
17 pistas significa Especialista?
Não.
O número de pistas é uma medida fraca de dificuldade humana quando usada isoladamente.
A dificuldade também depende de:
- distribuição das pistas;
- estrutura dos candidatos;
- técnicas necessárias;
- número de passos;
- profundidade de dependências;
- carga de reconhecimento.
Uma grade esparsa pode expor lógica simples.
Uma grade mais preenchida pode esconder uma cadeia difícil.
Por isso Mínimo de Pistas e Classificação de Dificuldade são páginas de Teoria separadas.
Um Sudoku de 16 pistas pode ter várias soluções?
Claro.
O teorema descarta apenas Sudokus clássicos únicos com 16 pistas.
Um estado inicial com 16 pistas ainda pode:
- ter várias soluções;
- não ter solução;
- parecer uma grade parcial válida.
Ele simplesmente não pode determinar exatamente uma solução clássica.
Por que isso importa para um gerador
Acima de tudo, o resultado mostra ao gerador o que não deve ser seu objetivo principal.
Um gerador prático deve buscar:
único
+ resolvível por lógica humana
+ dificuldade calibrada
+ variado
+ reproduzívelem vez de:
menor número de pistas possívelUm gerador obcecado por reduzir pistas ao extremo pode gastar muito processamento criando Sudokus matematicamente esparsos, mas não necessariamente agradáveis de resolver.
O número de pistas continua sendo um metadado útil.
Ele não é, sozinho, o objetivo de design.
Pesquisa vs jogo
O resultado das 17 pistas é fascinante porque descreve um limite rígido na estrutura combinatória do Sudoku.
Para jogar no dia a dia, a pergunta mais útil é:
Esta disposição exata de pistas cria um caminho de resolução justo e interessante?
São padrões de qualidade diferentes.
Perguntas frequentes
Qual é o menor número de pistas em um Sudoku clássico 9×9 com solução única?
17.
Existem Sudokus únicos com 16 pistas?
Não. O caso de 16 pistas foi descartado por uma busca computacional exaustiva.
Todo Sudoku com 17 pistas é difícil?
Não.
Todo Sudoku único com 17 pistas é minimal?
Sim, porque remover uma pista criaria um impossível Sudoku único com 16 pistas.
Todo Sudoku minimal tem 17 pistas?
Não.
Por que o número de pistas não serve para classificar dificuldade sozinho?
Porque as posições das pistas e a estrutura de deduções resultante importam muito mais do que apenas a quantidade bruta.
O que aprender depois
Leia Soluções Únicas no Sudoku para entender a propriedade global de uma solução.
Leia Como Sudokus São Gerados para ver o pipeline prático de remoção de pistas.