Qual é o número mínimo de dicas que um Sudoku pode ter?
Última atualização
Um Sudoku válido - com exatamente uma solução - requer pelo menos 17 dígitos fornecidos. Este é um resultado matemático comprovado. Qualquer quebra-cabeça 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 principalmente computacional: eles pesquisaram todo o espaço de grades possíveis com 16 pistas e verificaram que nenhuma produzia uma solução única. A busca 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 quebra-cabeças com 17 pistas haviam sido encontrados experimentalmente. A equipe de McGuire forneceu a primeira prova rigorosa de que 16 é impossível.
Como São os 17-Clue Puzzles
Os quebra-cabeças com 17 pistas são extremamente esparsos - 17 dígitos dados em 81 células, deixando 64 vazias. Eles estão entre os quebra-cabeças mais difíceis de resolver e normalmente exigem técnicas avançadas. Encontrar quebra-cabeças válidos com 17 pistas por si só exigiu décadas de esforço computacional. Até o momento da escrita, mais de 49.000 quebra-cabeças de Sudoku essencialmente diferentes com 17 pistas são conhecidos.
O Que Isso Significa para o Design de Quebra-Cabeças
Quebra-cabeças publicados voltados para solucionadores humanos raramente têm menos de 22 pistas. Quebra-cabeças de dificuldade Especialista e Mestre normalmente usam 22-27 dígitos dados, enquanto quebra-cabeças Fáceis usam 36-45. O mínimo de 17 pistas é um limite teórico - Na prática, a solubilidade com boa técnica e um caminho de resolução agradável importam muito mais do que a contagem de pistas sozinha.