Tuesday, November 14, 2006

Sudoku Solver finished!

I finally get my sudoku solver finished. While the bruteforce-backtracking variant is still not properly working, I completed the (in my opinion) more difficult one:
It's using Algorithm X by Knuth along with it's 'Dancing Links': That's a clever method for handling a spare matrix with a double-linked list, make changes to this matrix and later easily undo these changes. Algorithm X is non-deterministic alogrithm for solving an exact cover problem given in matrix form.
The point is now that: a sudoku puzzle can be transformed into an exact cover problem and therefore be solved with the algorithm X.
It took me really some time to understand how this all works, and even longer to implement it correctly (!), but it's pretty fast (much faster than the bruteforce-backtracking approach)! And once you understand it, it looks so elegant :-)
You can download the source from my site of course.

Apart form that, everything is fine. A lot to do for my study, but it's fun and quite interesting. A very good friend of mine moved into my flat, so now there is even more party in the evening.

And I want to emphasize it again: listen to Flyleaf. Such great music, I listened to them all the time while coding. So give it a try!

Ok, so keep on coding & reversing,