Sunday, February 26, 2006

Scheme Sudoku Solver

There is a Sudoku craze. Puzzles abound in books, newspapers, and web sites. For me, the charm fades as I wear out the eraser before the pencil when the inevitable backtracking occurs. But they are an interesting software exercise.

Every cell in a 9x9 sudoku puzzle is a member of 3 intersecting sets - a 3x3 box, a 9-cell row, and a 9-cell column. For a pending change in any cell, the rule must be applied to each of these 3 sets. Ergo, most of the effort is in applying the constraints.

I discarded my first attempt which looked too much like a 'C' program. The current one stores the puzzle in a vector. There are lists of vector indices representing different views of the puzzle space. The entire puzzle can be validated using the for-each idiom for a list of lists.

The source text can be found on this Schemely Wiki page.