An introduction

A common way to solve sudoku is by elimination of the impossible values in each cell. In general, whenever an algorithm cannot eliminate all but one possible value for a cell, a guess g needs to be made in order for the elimination algorithm to proceed. This guess may turn out to be a wrong one, in which case the algorithm must back trace to the state just prior to g and make another guess. Naturally, a way to measure the efficiency of a sudoku solver is the number of such wrong guesses, on average, it makes. The smaller this number is, the more "efficient" the algorithm is.

I tried to make my algorithm as efficient as possible. Try it out below! (The applet only works in 32-bit browsers.)

Your browser does not support the applet tag.

Of course, one may always doubt the number of guesses reported by the algorithm: who would let a student grade his/her own exam? One way to resolve this is for the algorithm to report, at each time it commits a cell to a certain value, the specific reasons behind it. For example, "(1,2) is assigned value 7 because value 9 is eliminated with reason 1, value 8 is eliminated with reason 2, etc." This functionality would be quite useful in terms of training a novice to get adept at solving sudokus. Not a bad idea as a companion software for national sudoku competitions, eh? :)

It's trivial to include this functionality as part of my algorithm. I'll get back to this... If you really desire such functionality, email me and I'll be happy to implement it.

Last updated: 08/14/2008