Generalized Sudoku Puzzle Solver Documentation

A standard Sudoku puzzle is a 9-by-9 matrix of cells, subdivided into 9 3-by-3 blocks, some containing digits between 1 and 9 inclusive. To solve the puzzle, fill the remaining cells so that each row, column, and block contains the digits 1 through 9.

The generalized Sudoku puzzle involves a k-by-k matrix of cells, subdivided into k m-by-n blocks, where k = mn, and the task requires filling the unfilled cells with the digits 1 through k so that each row, column, and block contains each of those digits.

This solver, written in C++, will eventually solve any Sudoku puzzle of any size, provided it is solvable. Note that as finding a solution to the generalized Sudoku puzzle is NP-hard, as the size gets larger the puzzle becomes effectively impossible to solve in a reasonable amount of time.

sudoku-cpp-0.1.tar.gz (link doesn't work yet!)

Although the general approach to solving Sudoku puzzles is simple and obvious (recursive backtracking), some coding ideas were taken from two prior Sudoku solvers: nihilist, Su Doku. Nihilist's in particular is interesting. Despite coding inefficiencies, the program is remarkably fast, so fast that I'm using it as a benchmark for measuring the speed of my own program (which is significantly slower for some puzzles).

To build a solver that uses a simple solution strategy (the default), type

make sudoku

in the src directory. See the Makefile (also in the src directory) for different strategies and further options, such as profiling.

To test a successful build, type

./sudoku <rows> <columns> <puzzleFile>

in the src directory, where "rows" and "columns" denote the number of rows and columns, respectively, in a given block of the puzzle, and "puzzleFile" denotes the name of a puzzle file for solving. The order of the arguments matters: for example, it may be that an 8-by-8 puzzle is solvable if interpreted as containing 2-by-4 blocks, but not if interpreted as containing 4-by-2 blocks.

The src/samples directory contains puzzles of various sizes to choose from.