Dr. Who’s Sudoku Solver and Rating Program

To the denizens of Iron Sudoku I am known as drwho, the player who posts a difficulty score for the daily puzzle. The Iron Sudoku web site publishes a new puzzle each day with a difficulty ranking of Easy, Medium, Hard or Expert. This ranking is based on the most advanced solution technique required to solve the puzzle. Often the players comment in the chatterbox that a “Hard” was actually quite easy, or sometimes a “Medium” was devilishly hard. The score I provide is an attempt to provide a more accurate difficulty rating. It can be thought of as a number that indicates how long the puzzle will take. However, some players are faster than others, so the best I can hope is that the difficulty score when multiplied by a number that represents your speed or skill level will be a fairly good predictor of how long the puzzle will take you. To give some context to the numbers, I have created a table of scores for the Iron Sudoku puzzles.

The scores are generated by a program I wrote that can solve the puzzles and/or provide a difficulty rating. For those of you who are programmers, here is the source code. It is written in C, designed to run on a Linux or Unix platform. If you have Cygwin installed on your PC you can compile and run it under Windows. Unfortunately it is not a Windows program. Rather, it is a command line program that uses the curses library to generate character graphics on a standard dumb terminal. Also included, is a version of the program (sudokuCGI) with the curses interface replaced with a CGI interface.

Online Solver

This is a link to an online version of my solver program. The user interface is implemented as a JavaScript on the browser side. The solution logic and difficulty evaluation program runs on the server side and is my original C program with the curses interface replaced with a CGI interface (see above – sudokuCGI.c).

Bookmarks

While I usually post the difficulty score for the daily puzzle at Iron Sudoku in the Chatterbox shortly after the puzzle is posted, I may not be able to do so until late in the day or maybe several days later on this web site. If you wish to know my score but I haven't posted it yet, you no longer have to wait for me to post it. I have created a script that you can use to get the score for yourself. In fact I have created another script that you can use at the Web Sudoku site. I may add other scripts for other websites if there is interest. Leave your requests in the feedback form. Below are links to the scripts and instructions on how to create a bookmark that you can use at the supported Sudoku sites.

Players at the Iron Sudoku website often use a JavaScript applet they refer to as the auto-green script. The source of the original script was the player known as brittlefish and the script could be found at his website. The site is gone and the latest version of the script no longer works because it refers to the now defunct brittlefish.com website. I have rewritten the script and you can get it here:

Scoring Algorithm

For those of you who don’t read C or would rather not, here is an explanation of the scoring algorithm. The program scans the grid first using cross-hatching on the blocks. If that doesn’t turn up anything it scans the grid again this time cross-hatching the rows and columns. If that doesn’t turn up anything it scans the grid using the missing digit technique. Again if that doesn’t turn up anything it repeats the scan using virtual cross-hatching. If that fails the next strategy is tuples analysis which is a combination of naked pairs, hidden pairs, triples, quads, and so on. As a side note, the program uses essentially the same algorithm to effect all those techniques plus virtual cross-hatching. Tuples analysis proceeds by trying the simplest technique first (naked pairs) and then trying the other tuples techniques in order of increasing difficulty (hidden pairs, naked triples, hidden triples and so on up to naked and hidden octuples, if necessary) until a positive result is obtained. If all those strategies fail, the program resorts to guessing.

Now for the scores, cross-hatching on a block is worth 1 difficulty point. Cross-hatching a row or column is worth 2 points. A missing digit scan is worth 3 points. Virtual cross-hatching is worth 4 points. Naked and hidden pairs are worth 5 points, triples 6 points, quads 7 points, and so on up to octuples at 11 points. A guess is worth 12 points. Each pass through the grid, the score is incremented by the value of the least complicated technique needed to make progress. As you can see, a puzzle that doesn’t require advanced techniques can nevertheless get a high score if it takes many passes through the grid to solve the puzzle. And it might be possible for a puzzle which requires advanced techniques to get a relatively low score if the solution is achieved with only a few passes through the grid.

Is Guessing Cheating?

Now a few words about guessing, some people think it is cheating. Not at all! While it is not very satisfying, it is a legitimate technique. In the general case (grids of arbitrary size), Sudoku has no finite set of solution techniques, so guessing is necessary to solve the general problem. Even for the normal 9x9 grid, the number of techniques is large and I don't know that anyone has enumerated all of the techniques necessary to solve every possible 9x9 puzzle. So unless you do know all the techniques, you will have to guess sometimes.

If there were no other techniques available, solver programs might be a little slow, but with the speed of modern computers it is possible to do an exhaustive search (e.g. guessing). By combining guessing with just a few simple analysis techniques (essentially pruning the search tree) it is possible to solve any 9x9 sudoku puzzle virtually instantly with just a PC. My progam uses guessing to eliminate possiblities. If a guess yields a solution, the program considers that guess a failure, nothing was learned. If a guess leads to an impossibility the program can eliminate a candidate (the original guess) from a cell. If 2 distinctly different guesses both yield solutions then the puzzle does not have a unique solution and the program quits searching.