Sunday, August 28, 2005
Yesterday I ran across a kind of logic puzzle known as Sudoku. For more information, see the Wikipedia article about it. This type of puzzle is apparently becoming very popular among those who enjoy working puzzles in newspapers.
I have no interest in such puzzles, but I thought it might be fun to write a program that would solve them, and it would be a good chance to learn more about Ruby. So I went at it for a few hours, and wound up with a working program. It implements a simple brute-force depth-first search algorithm—I wasn't interested in doing anything clever. It solves the example puzzle from the Wikipedia article in about five seconds on my iMac G5.
If anybody is interested in playing around with it or improving upon it, it can be downloaded from http://kristopherjohnson.net/download/sudoku.tar.gz. (Of course, you will need Ruby installed to run it.)
As input, it takes a list of nine nine-character lines. Use the digits '1' through '9' to represent the givens, and the character '.' (period) to represent empty squares. For example, if you want to solve the puzzle from the Wikipedia article, create a file wikipedia_example.txt and give it these contents:
53..7.... 6..195... .98....6. 8...6...3 4..8.3..1 7...2...6 .6....28. ...419..5 ....8..79
Then run the solve_sudoku.rb program, like this:
ruby solve_sudoku.rb wikipedia_example.txt
and you'll get this output:
534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179
I used test-first design, so a set of unit tests is included. This is the kind of very-simple program where I would normally be tempted to just dive in without doing any unit testing, but I'm glad I did this one test-first. I'm still learning Ruby, so I made several dumb syntactic mistakes, and it would have been very difficult to catch them if I'd tried to write the whole thing at once and then debug it.
By the way, using Ruby is a lot of fun. (Yes, Sean, I know you told me so.)
I was teaching a class on Thursday and Friday and during one of the breaks, I noticed one of the students was carrying a "sudoku for dummies" book. She told me about the craze.
Sandy and I read sudoku article by Will Shortz in the New York Times this morning. I spent about two hours playing the puzzles that I found on Web Sudoku.
That is until I got distracted by the Hurricane Katrina coverage on CNN. Turns out I may very well get deployed later this week. I guess I know what I'll be doing in my off hours.
I made no attempt to make the thing fast. I use strings as my underlying data structure--it might be faster if arrays were used instead.