Uma escala para medir a dificuldade dos quebra-cabeças de Sudoku

Resumo

Nos últimos anos, o Sudoku tornou-se um jogo muito popular, merecendo a atenção de muitos investigadores. A maior parte dos puzzles de Sudoku é classificada como simples, média ou difícil, consoante o seu grau de dificuldade. Contudo, quando questionados acerca do critério de classificação, não existe uma resposta clara. Este artigo apresenta um método manual para medir o grau de dificuldade dos puzzles de Sudoku. Ao contrário de outros métodos, este método classifica os puzzles automaticamente, sem intervenção humana. A escala utilizada é inspirada na escala utilizada nas pistas de neve: verde, azul, vermelho e negro. O puzzle de Sudoku é transformado num problema de SAT e o nível de dificuldade é dado pela resolução do problema de SAT, o qual é equivalente ao da resolução manual. O classificador de dificuldade e um conjunto de puzzles de Sudoku classificados estão disponíveis na Web.