Sudoku Difficulty Ratings
How do we rank the difficulty of Sudoku puzzles?
Many newspapers and Sudoku sites rate their puzzles simply on how many values there are in the grid to begin with. After all, the more you’re given, the easier it must be, right?
Well sometimes that’s true (and it is for the easiest puzzles), but after playing many many Sudoku by hand with pencil and paper, I found that the really difficult puzzles were those that required use of more challenging techniques to be able to solve them.
Our puzzles are rated as follows:
|Level||Average Difficulty Score|
Sudoku Rating Method
The scores for each puzzle are determined not just by how many cells there are to fill in, but also how many different techniques it takes to complete them, and how many times each one is used.
The most difficult puzzles of all are the ones that require a very wide range of the most challenging techniques – and for these the difficulty of the techniques far outweighs the number of cells to fill in!
Techniques and Costs
Our solver goes through a puzzle like a human player would – it looks for the easiest opportunities first, and then only if it can’t spot an easy technique to make some progress, steps up and tries more and more complex tools on the puzzle until it finds one which works and allows progress again.
It cotinues to do this until the puzzle is solved – or if it can’t find a technique that will work, it will declare the puzzle unsolvable by logical techniques! It’s always possible that it is solvable by other techniques, as people have devised lots of their own weird and wonderful methods! The computer solver doesn’t use guessing (nishio), or the ariadne’s thread technique to solve the puzzle as those aren’t methods that are usable by normal human players – though we’ve had a few rare people get in contact to say that they do use them too.
We assign each technique a “cost” to use. The higher the total cost, adding up over the whole solution, the harder the puzzle!
We also decided that the first use of a technique is usually the hardest, but that if you understand the technique, then applying it again won’t be quite such a hard step, so the cost for subsequent uses is lower for the harder techniques.
Here, if you’re interested, are the scores that we use for each of the techniques:
|Technique||Code||Cost for first use||Cost for subsequent uses|
Sometimes the puzzles are slightly harder or easier, because of differences in how many of each technique are required. There’s a wide spread of difficulties, but to fit them into easily understood difficulty categories they are grouped within a certain range.
Eagle-eyed readers will spot that these ranges have some overlap – the most difficult Medium puzzles would be similar to the easiest Tricky puzzles – this is deliberate, because it allows the generator an extra bit of leeway as it works to create a puzzle that’s still within an acceptable range.
|Level||Lowest Difficulty Score||Highest Difficulty Score|
This method of evaluating Sudoku difficulty came about after a great deal of thinking (and a lot of coffee!). At a time when most developers were making computer generated sudoku with no thought to the actual human solving difficulty, this was quite a breakthrough. It was originally proposed and explained on the Sudoku Programmers Forum, in Summer of 2005, and the general method has been used by a number of programmers since!
How Do We Create Sudoku?
Because we want to create a Sudoku which has a difficulty in a particular target area, we use a Reductive method. We played around with a few methods, and we found that this was the best method for creating Sudoku – at least for us!
Our creator is actually a wrapped around our solver, so we work by trying lots of puzzles until we get to one which we can solve and fits the kind of puzzle that we want.
Here’s how it works: