My Sudoku Program

[Thinking Skins]

Hey everybody, I just finished writing some Sudoku scripts for my web page (www.learninglover.com). I figured I'd share them. I also wrote a blog entry about the method I used to solve the problems. Its based on an implementation of backtracking and the dancing links algorithm. The blog entry is available at http://learninglover.com/blog/?p=98 and the actual sudoku program (which you can link to from the blog) is available at (http://www.learninglover.com/examples.php?id=10).

This was a pretty fun experience. As most of you know, I'm a mathematician and I love playing around with different problems and trying to figure out how to solve them, or when somebody else has solved a seemingly difficult problem, I like to see how they solved it. Dancing links is an algorithm that seems to work pretty fast in practice when compared to other solvers so I wanted to see it in action and its pretty nice.

Take a look at it if you get a chance.

[PokerPacker]

I had to write a sudoku solver a few years back, but it was a simple trial and error method.

[Thinking Skins]

When I initially started working on this, it was going to be something like that, but I thought that might be too tedious to keep track of. I started reading up on other ways to do it and saw this dancing links representation that looked good and I wanted to give it a shot.

Anybody who's had a class in programming can basically do it. Its just a linked list. But instead of being one dimensional (ala a list) its two dimensional (ala a matrix) and its bi-directional and circular. But this is the stuff you learn about in a programming 2 or data structures class. Then trial and error become simple procedures of inserting and deleting elements from this matrix, and you can do a much simpler iteration through all possible solutions.