Sudoku preview

The solver for the Sudoku game was a fun challenge.

At it base, the solver is a brute force, recursive algorithm. But the most simple version is O(n^n), which is obviously not acceptable for a 9×9 table. There are a few optimizations that rescue it though.

The first is obvious, start by eliminating possibilities across the horizontals, verticals and blocks anything that conflicts with initial values.

The second trick is really neat. Instead of walking through the Sudoku board left to right, top to bottom fashion, or whatever arbitrary pattern you might come up with, you start with the square with the fewest remaining possibilities, then go to the next lowest and next lowest and so on. This was your tree has the fewest branches at the top and the most at the bottom, you end up with many, many fewer test solutions to try out.

I wish I could take credit for that solution, but I had to search for it and found it here.

For now, it shows off some basic programming skills in JavaScript, mainly Object Programming and general familiarity with the language, as well as manipulating the DOM with jQuery.

The next thing I would like to do with it is to offer a more beautiful html5 canvas ui and work in some animation. I’ve also been thinking about writing the board library in php, or putting it in a database and loading it in using ajax.

My Sudoku Game

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>