Sunday, August 28, 2005

 

Sudoku Solver

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.)


Comments:
I went to a bookstore in Grand Rapids, Michigan on Wednesday night. While I walked by the games section I saw that it was completely taken over by sudoku books. I had never seen the puzzle, but I noted it as a new craze.

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.
 
The Times article is what prompted me to look into sudoku.

Good luck with your emergency duties.
 
weird ... the first draft of a sudoku solver i did in java needed mere milliseconds on my iBook G4, and i must have implemented a similar algorithm. i doubt ruby is so much slower. i wanted to have a look at your code (would've been a funny excercise as i don't really speak ruby), but the archive is no longer online :-(
 
The archive should be available now.

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.
 
You can find a sudoku solver on www.sudoku.org.es.
 
There is a challenging sudoku puzzle at Domo-Sudoku.com
 
Post a Comment

<< Home

This page is powered by Blogger. Isn't yours?