Sudoku

Some months ago, as an academic exercise, I decided I needed to write a program to solve Sudoku puzzles. I had wanted to write one, and I wanted an exercise in test driven development, so I got started.

First of all, no one should be too impressed that anyone can write a working program to solve Sudoku puzzles. Any undergrad CS student should be able to crank one out. It’s really not that hard.

“Test driven development” (or TDD) means that I started not by writing the Sudoku program itself, but by writing a series of little programs, called unit tests, that check whether my Sudoku program behaves correctly. I would write a unit test first and get it to fail, and then update my program just enough until the unit test passed. The first unit test just stored digits in a 9x9 grid and spit them back out. That’s all. The next test checked whether the grid represented a “valid” Sudoku grid or not – did the same digit appear more than once in any row, column or 3x3 box? Lather, rinse, repeat.

Within a couple hours, and several test iterations, I had a functioning Sudoku solver. It used only a “brute force” strategy but it worked. I had several test puzzles that I copied from newspapers, and there was one puzzle that was particularly difficult for this brute-force strategy. It took my computer about 7 seconds to solve that puzzle. Not bad eh?

Actually, I knew it wasn’t very good at all. Seven seconds is an eternity in CPU cycles. I had planned to add different strategies to the program, which I knew would speed things up. But first I wanted to see what improvements could be made using the same strategy. TDD can be good for getting things to work, but TDD alone won’t get them working in the best possible way. However, once you have things working, TDD does provide you with a good set of regression tests, so you can make improvements without worrying about whether you’ve broken anything.

This was a good opportunity to learn about the profiling tools in Eclipse. I ran my program, and then used the profiler to find out where the program spent most of its time. My initial implementation was copying groups of values from the grid, and then checking them against the puzzle rules. Why not check them in place instead? I worked out an indexing scheme so the checks could reference values from the grid without copying them. This improved performance by about 50 percent – the tough puzzle was solved in about three seconds.

It was time to add a new strategy to the mix. At each step of the solution, before using the brute force strategy, I wanted the program to see if there were any rows, columns, or boxes with only one empty value. If it found one, it would be easy to determine which value belonged there. My first implementation of this strategy improved performance on the tough puzzle by nearly one order of magnitude, to 0.4 seconds.

I went back to the profiler output. Then I realized that it was ridiculous to recheck every row, column and box at every step of the solution. With a small bit array for each row, column and box, I could keep track of which values were filled in, and which digits were used, as I was going. For a small amount of memory and a little extra bookkeeping, the checks for this strategy were sped up immensely. I got nearly another order of magnitude improvement on the tough puzzle, down to about 0.04 seconds. That’s better than 7 seconds, right?

I haven’t touched the Sudoku program now in three months. At some point, I would still like to introduce other strategies. The ultimate goal is a solver that can tell me not just the solution, but also how a human would have solved it. Along the way, this little project helped me to learn how TDD can enable quick functional solutions and support subsequent refactoring. Not all code requires the level of scrutiny I put into this program, to drive out performance bottlenecks, but TDD alone will not produce the most efficient solution. Development teams using TDD should review their solutions against performance requirements, identify potential bottlenecks, and then refactor their solutions carefully to achieve the desired non-functional behavior.