Difficulty Rating for Sudoku puzzle

Introduction

A reader left a comment in How to write a sudoku generator. He was asking how to generate puzzles of varying difficulties such as easy, medium and hard. This is impossible without a difficulty rating system. Therefore we are going to write a sudoku rater that would give a difficulty rating to a puzzle.

The First Rating System

We are going to implement the following rating :

• -1 means no solution (this is an error case)
• 0 means easy, this means the puzzle is solvable using the method of elimination only
• 5 means hard, this means the puzzle must be solved by guessing (method of recursion)

Enhance Rating System

To enhance the rating system, we must enhance the solver too. Previously we have only two methods for solving, the method of elimination and the method of guessing. There are actually many other logical methods for solving the puzzle. You may google for the sudoku solving techniques such as "naked pair", "hidden pair", and "x wing". As an example, I am going to implement the "naked pair" method in the solver. The rating system now become :

• -1 means no solution
• 0 means easy, this means the puzzle is solvable using the method of elimination only
• 3 means medium, this means the solver must apply the method of "naked pair"
• 5 means hard, this means the puzzle must be solved by guessing (method of recursion)

You may further enhance the system if you implement a harder rule such as "x wing" and give a rating of 4. However, for simplicity and demonstration purpose, I will only implement "naked pair" here.

Naked Pair Method

You may google for "sudoku" "naked pair" for a more detailed description. I will just give an example below
Consider the following rows with possible values filled :
| 236 | 23567 | 24567 | 2678 | 2678 | 9 | 67 | 1 | 67 |

Since column 7 and column 9 contains only two digits {6,7}, we know that all other columns cannot contain 6 and 7, hence we may eliminate them :
| 23 | 235 | 245 | 28 | 28 | 9 | 67 | 1 | 67 |

Now {2,8} is only possible on column 4 and 5, we can further eliminate :
| 3 | 35 | 45 | 28 | 28 | 9 | 67 | 1 | 67

Now we have solved the digit 3 in column 1, we can further eliminate :
| 3 | 5 | 45 | 28 | 28 | 9 | 67 | 1 | 67
Note that the above elimination is known as "method of elimination" in our solver, it is a "easy" method and is separated from the "Naked Pair" method.

Digit 5 is newly solved, further eliminate :
| 3 | 5 | 4 | 28 | 28 | 9 | 67 | 1 | 67

Digit 4 is newly solved, cannot eliminate further

Sample Puzzle

Difficult :
    String puzzle = "7........"+
                    "....8...1"+
                    "64......."+
                    "........."+
                    "..8....2."+
                    "........."+
                    "......9.."+
                    ".....1..."+
                    ".........";

Medium :
           puzzle = "91...7.54"+
                    "8..1.49.."+
                    "....3...8"+
                    ".4....315"+
                    "3.......9"+
                    "159....6."+
                    "2...1...."+
                    "..17.9..6"+
                    "48.5...91";

Easy :
           puzzle = "..42.8..5"+
                    "..1.6...7"+
                    "8...3..2."+
                    ".439..168"+
                    "...456..."+
                    "276..145."+
                    ".3..1...2"+
                    "4...2.5.."+
                    "6..8.97..";


You may try to feed all of the above puzzles to the rater below

Source Code

As usual, almost all posts here will end with a full runnable demonstration :