Qual é o número mínimo de pistas que um Sudoku pode ter?
Última atualização
Um Sudoku válido - Aquele com exatamente uma solução - Requer pelo menos 17 dígitos fornecidos. Este é um resultado matemático comprovado. Qualquer puzzle com 16 ou menos pistas tem múltiplas soluções ou nenhuma.
A Prova de 2012
Em 2012, Gary McGuire, Bastian Tugemann e Gilles Civario da University College Dublin publicaram uma prova de que não existe nenhum Sudoku válido com 16 pistas. O trabalho deles foi essencialmente computacional: pesquisaram todo o espaço de grelhas possíveis com 16 pistas e verificaram que nenhuma produzia uma solução única. A pesquisa exigiu aproximadamente 7 milhões de horas-núcleo de computação.
Antes disso, acreditava-se amplamente que 17 era o mínimo e milhares de puzzles com 17 pistas tinham sido encontrados experimentalmente. A equipa de McGuire forneceu a primeira prova rigorosa de que 16 é impossível.
Como São os Puzzles de 17 Pistas
Os puzzles de 17 pistas são extremamente esparsos - 17 dígitos dados em 81 células, deixando 64 vazias. Estão entre os puzzles mais difíceis de resolver e normalmente requerem técnicas avançadas. Encontrar puzzles válidos de 17 pistas exigiu décadas de esforço computacional. No momento da escrita, são conhecidos mais de 49.000 puzzles de Sudoku de 17 pistas essencialmente diferentes.
O Que Isto Significa para o Design de Puzzles
Os puzzles publicados destinados a solucionadores humanos raramente têm menos de 22 pistas. Os puzzles de dificuldade Especialista e Mestre usam tipicamente 22-27 dígitos fornecidos, enquanto os puzzles Fáceis usam 36-45. O mínimo de 17 pistas é um limite teórico - Na prática, a capacidade de resolução com boa técnica e um percurso de resolução agradável são muito mais importantes do que a contagem de pistas por si só.