Sudoku Grader

In fact, analyzing and grading puzzles is a task perfectly suited to number-crunching, always impartial, infallible geniuses—computers. All that is required is an algorithm to follow, and the computer will do all of the rest of the work. So the first step in creating a Sudoku grading scale is deciding on an algorithm. The question that must be asked is this: what makes a Sudoku puzzle difficult? Difficulty can be decomposed into two basic categories: strategic and procedural. Strategic difficulty refers to the difficulty of the techniques used in solving the puzzle, while procedural difficulty refers to the difficulty of the progression through those techniques. For instance, a puzzle might require one of the most difficult strategies, but only use it once, thus having a low procedural difficulty despite a high strategic difficulty. These two categories form the basis for the final difficulty score.

With these criteria in mind, one can begin to create the skeleton of a grading system. The computer will take a puzzle, and attack it with the solving techniques one at a time. First it will attempt to apply the easiest technique, but if it cannot do so jump up to a more difficult strategy, and continue this until a strategy is applied. The program will then start over with the easiest technique in case the application of the previous technique resulted in making an easy strategy usable. The program will continue in this manner until either the puzzle is solved, or it runs out of solving techniques to apply. After the solving is complete, by examining which strategies are used a strategic difficulty score will be calculated, and then a procedural difficulty will be calculated by analyzing the steps taken. It appears easy enough, but there are some complications.

Using this grading algorithm, one immediately runs into a significant problem. Who is to say how difficult strategies are in comparison with one another, and how can one be certain that the grading system takes into account every possible Sudoku solving strategy? These are thorny issues that cannot be rectified, so some concessions must be made. First of all, there are tens of strategies for solving Sudoku puzzles. As long as all strategies below a certain plateau of difficulty are covered, it is not a problem that not all strategies are implemented. If a necessary strategy is not used by the computer, resulting in an unsolvable puzzle, one can simply give the puzzle the highest difficulty score available. On the second front, one needs to break down the common solving strategies into comparable categories.

There are two categories of strategies: strategies that result in a cell in the Sudoku grid being assigned a value and those that result in possible candidates for a cell’s value being removed. Peter Gordon, author of The Mensa Guide to Solving Sudoku, suggests a certain progression through these categories when solving Sudoku puzzles. The first category tends to be the easiest. It includes strategies, in order from easiest to hardest, like Simple Singles, Slicing and Slotting, Singles, and Hidden Singles. The second category is more difficult, including strategies, again in order from easiest to hardest, like Locked Candidates, Naked Subsets, Hidden Subsets, and advanced strategies like X-Wing and Swordfish. With the strategies identified, all one has to do is understand the strategies, and then decipher how to program the computer to follow them.