random memes }


Last week was helping my 10 year old daughter with her math homework. The assignment was to solve a Sudoku puzzle. In fact, I was there more for moral support as she did not need any help. I had shown her in previous assignments how to solve a Sudoku puzzle using sets. She whizzed through the puzzle, got to the very end, and realized there was a mistake .... somewhere.

Rather than re-solve the puzzle manually, I wrote a Sudoku solver. Probably nothing unique about this - I would bet this is a common-enough exercise in programming courses. Still, as an application that ran in-page in a web browser, this gave me an excuse to exercise DHTML and Javascript in a slightly different way than anything I'd done previous.

The default puzzle is in fact my daughter's last homework assignment. Each cell as shown contains either the value, or a set of possible values. You can edit, save, and bookmark the initial set of known values. For example, a variant with fewer knowns offers an example of an edited and bookmarked puzzle. Looks like I need an additional algorithm. Here is a puzzle the solver cannot solve though it can with a single additional known value. Since the objective was a means to check my daughter's homework, this is good enough.

Enable access to the test functions, and you can exercise the individual steps in the solver algorithm, and time the overlap solver.

One interesting bit - in IE7 the Javascript code for this algorithm runs in about half the time of taken in Firefox.