Tuesday, May 6, 2008

Fun with Sudoku

In a previous life, I was interested in Sudoku for a while. I never got into doing the puzzles, but I wanted to write a Sudoku solver in Python. It seemed like a fun problem, and it is not too hard, until you get to puzzles which have no two-way decision points where one decision leads to an invalid puzzle, forcing the other path. Then I stumbled across this. Naturally, Peter Norvig is way smarter than me, that's one reason Google pays him so much. If you don't believe me, watch this. Norvig says: "as computer security expert Ben Laurie has stated, Sudoku is "a denial of service attack on human intellect." That sounds about right to me.

Anyway, while I was thinking about Sudoku, I read the Wikipedia entry. It says: "The numerals...are used for convenience...any set of distinct symbols will do, such as letters, shapes or colours." And that got me thinking... I ended up writing a Cocoa application for Color Sudoku. At the time (late 2005), nobody else had implemented one that I could find on the web. However, a quick Google search shows that the situation has changed.

Still, I don't think anybody has done it like I did. It is so long ago that I really don't feel like reading through the code. Like many projects, it grew without apparent direction. But the app still works under Leopard and it is fun to play. It is in my public folder at .Mac. There are other goodies there as well. Here is a screenshot:

Each number is represented by a different color. If a given position in the 9 x 9 grid is completely determined, it is filled in with a solid color. Otherwise, the possible values for the square are given as smaller squares. You click on squares to make them go away, when you deduce that they are not possible values (or command-click to select one). I find it very easy and intuitive to play, and it beats the heck out of crossing out numbers.

I notice that the version in the folder does not bring the window back with command-N. I only learned how to do that later.

One more point. There is a lot of Perl used for Bioinformatics. As far as I can tell, there is no reason to write any new project in Perl. I know it is partly a matter of taste. Still, this guy is very proud that his Perl Sudoku solver is only four lines of completely obscure code (actually, I see he has made it three lines now). Not all Perl is like this, but I found that after a week or two, I simply could not understand how my programs worked without a lot of effort. It's not like that in Python. Here are a couple of citations on point:
Programs must be written for people to read, and only incidentally for machines to execute.

- Abelson & Sussman, SICP

How do we convince people that in programming simplicity and clarity—in short: what mathematicians call "elegance"— are not a dispensable luxury, but a crucial matter that decides between success and failure?

- E. W. Dijkstra