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.

A good standard grading scale would run from 0 to 10. Because mankind operates in a base 10 world, this scale just plain makes sense. The largest factor in determining whether or not an individual can solve a puzzle is whether the individual knows enough strategies to solve it. If one does not know the strategy, one cannot apply it, and the Sudoku cannot be solved. For this reason, allocate 7 of the 10 points in the grading scale to strategic difficulty. A 7 will be given when the program does not have enough strategies in its arsenal to solve the puzzle. Otherwise, the puzzle will assume the strategic difficulty score of the most difficult strategy it uses. A 6 will be granted if X-Wing or Swordfish are used. A 5 will be granted if Hidden Quads are used, as they can be extremely difficult to spot. A four will be given if a Naked Quad, Hidden Triple, or Hidden Pair is used. A three will be given to Naked Pairs and Naked Triples. Naked subsets are quicker to spot than hidden subsets, thus a Naked Subset the same size as a Hidden Subset will have a lower score. Finally, a two will be given if Locked Candidates are used, a one if Hidden Singles or Singles are used, and a zero if only Slicing and Slotting and Simple Singles are used. These last two strategies are quick to spot and do not require keeping candidate lists, and thus carry the lowest difficulty rank. With strategic difficulty assigned, now the program can assign procedural difficulty scores.

A procedural difficulty score is more difficult to assign because individuals solve puzzles in different ways and tend to take different paths when approaching the same Sudoku puzzle. That said, there are a couple of universal factors that will make a puzzle procedurally difficult. First is the number of candidate elimination strategies used. If the bulk of strategies used to solve a puzzle do not result in any values being placed, an individual solving the Sudoku will have a much harder time. So if more than four candidate elimination techniques are used, one can add one to the procedural difficulty score. If eight are used, the puzzle is especially difficult, and another procedural difficulty point can be tacked on. The second problem that will make a puzzle procedurally difficult is its sheer length. This can be measured by counting the number of empty squares in the puzzle. If there are more than 55 squares to solve, a final procedural difficulty point may be added. This results in a total possible procedural difficulty score of 3, which adding to the strategic difficulty score, will give a score out of 10. The grading scale is complete