Rating Logic Puzzle Difficulty Automatically in a Human Perspective

This paper proposes a method for rating the difficulty of logic puzzles from a human perspective, using Sudoku as the test case. The authors argue that difficulty is among the most important design factors for puzzles, since problems that are too easy bore players and problems that are too hard frustrate them. Their goal is a general, game-independent difficulty measure that can rank both human-designed and randomly generated problems, and that can be applied to newly invented puzzles without heavy manual analysis. The work situates itself against prior Sudoku difficulty research, much of which relies on game-specific strategy counts or purely computational complexity measures that are not tied to how people actually play.

The method models a puzzle's possible states as a search tree and derives features from the solving path taken by a beginner-level solver that uses only basic single-candidate techniques, with guessing and backtracking when needed. Five features are considered: the number of basic calculations, the number of guesses, the number of backtraces, the average number of certain next moves, and the average number of uncertain next moves. A second-order polynomial combining these features is evolved with a genetic algorithm so that its ranking matches average solving times drawn from online Sudoku play records. The best function reached a Spearman's rho of 0.8 on training data and 0.69 on a validation set of 150 problems, which the authors describe as somewhat weaker than game-specific methods but more flexible in scope.

Analysis of the evolved function suggests that uncertain branches increase difficulty, certain branches reduce it, and guessing and backtracking contribute positively, while the raw count of calculations appears less influential. The authors interpret these findings as guidance for designers, particularly regarding limits on consecutive uncertain moves. The study is limited to a single game and a single solver profile, and the authors acknowledge that optimal parameters vary across games. Future work is proposed to examine player experience under gradually increasing difficulty and to extend the criteria to non-logic games such as visual-search puzzles.