Como se mede a dificuldade do Sudoku?

A dificuldade de um puzzle é definida pela única técnica de lógica mais difícil necessária para resolvê-lo sem chutar. Solvers como o Sudoku Explainer percorrem um puzzle com uma escada fixa de técnicas — dos singles nus até as cadeias forçadas — e reportam como um número o degrau mais difícil que precisaram usar, o grau SE. Como o método é fixo e reproduzível, o mesmo puzzle sempre recebe o mesmo grau — e é por isso que avaliamos cada tabuleiro assim, em vez de usar palavras vagas como "fácil" ou "expert".

Não de forma confiável. O menor número de pistas que um Sudoku válido pode ter mantendo exatamente uma solução é 17 — provado por uma busca computacional exaustiva (McGuire, Tugemann e Civario, 2012). Mas a contagem de pistas só acompanha a dificuldade fracamente: um puzzle de 17 pistas pode ser suave, e um de 30 pistas pode exigir cadeias avançadas. O que importa é a técnica que o arranjo obriga, não o número de espaços em branco.

Existem 6,670,903,752,021,072,936,960 — cerca de 6.67 × 10²¹ — grades de Sudoku totalmente resolvidas (Felgenhauer e Jarvis, 2005), que se reduzem a 5,472,730,538 essencialmente diferentes depois de remover a simetria. Na prática, isso significa que puzzles novos, nunca vistos antes, em qualquer dificuldade, nunca vão acabar.

'Monstros' famosos como o AI Escargot (Arto Inkala, 2006) já foram anunciados como os mais difíceis já feitos. O grau SE permite compará-los de forma objetiva, e não por reputação: os puzzles mais difíceis que se conhecem ficam em torno do grau SE 11 e acima.

Veja como funciona o grau SE ou os puzzles de Sudoku mais difíceis para ver a lista completa de monstros.