The Omnifarium - Sudoku

Notice

I am no longer posting new puzzles to this blog. For all of my Sudoku puzzles, old and new, please visit Sudoku in another section of this website. I will still create and offer new puzzles, in batches of a couple of hundred, once a week or so.

Sudoku #34

Category: Sudoku
Thu, 28 Jul 2005, 08:53

Previously, I talked about rewriting my Sudoku program from Python to C to improve its run-time performance. Not content to leave well enough alone, I decided to try to improve performance a bit more by tweaking the algorithm.

(The following discussion is probably of interest only to computer programmers. For others, feel free to skip ahead to todays puzzle.)

First, let me summarise how I first implemented the basic Sudoku solving methods. Function set_cell() is called to set the value of a cell. Function eliminate() is used to eliminate a possibility from a cell. And function resolve() locates a cell in a group with a unique possibility within the group. The three functions were mutually recursive. For example, function set_cell() would call eliminate(), which might then call set_cell() if the number of possibilities for a cell dropped down to 1.

The performance enhancement I wanted to try was to just consider the unknown cells within a group, rather than all of them. The idea was that each group would be partitioned into two areas. When a cell gets set a specific value, the cell would be then be moved into the bottom half of the group, and further analysis would then consider just the unknown cells at the top of the group.

Unfortunately, the recursion of the three basic functions meant that cells would get set and unique possibilities searched for before certain possibilities were eliminated from all of the cells of a group. Which meant that function resolve() could see a unique possibility in the unknown portion of a group where the possibility was already set in the known portion. This caused the program to blow up real good.

The answer was to implement another performance improvement, changing the recursive algorithm into an iterative one. Function eliminate() would now eliminate possibilities from all cells of the group before proceeding. If new cell values get discovered, they would get added to a list, to be processed on a subsequent iteration of the loop. One reason this would help performance is that function resolve() would not get called multiple times as the recursive calls wound back down the call stack.

What kind of improvement did I get from these two changes? My old program could generate about six puzzles per minute. The new one could now produce about 28 puzzles per minute. That's more than a four times improvement!

With this one application, I've now demonstrated three ways you can improve performance in your code: First, use a compiled language; second, find a better algorithm; and third, convert a recursive algorithm into an iterative algorithm.

And now, on to todays Sudoku puzzle.

Hans

path: /Sudoku | permanent link to this entry