Sudoku solver in C [Linux]

When I was in first year of my study (now in 3rd) at my college, Yuvarajaa and I wrote a C program to solve sudoku. The program solves it much the same way as we humans do. There is no brute force used.

To download the source code go here. The instructions for compiling are also given in the same page. I explain the algorithm used below.

Sudoku is a type of Latin square and an exact cover problem and efficient algorithms to solve it can be written using methods like backtracking or dangling links. But our algorithm is very simple(meaning beginners can understand. We ourselves were beginners then:-)) which solves it pretty much the same way as we humans do. Consequently our algorithm is slower than above mentioned ones.(It is still much faster, given the capabilities of today's PCs & you wont notice a difference.)

The program does following things in the given order:

1. Enumerates possible values of all empty cells. The cells which have only one possible value are filled up.
2. Next the enumerated values are scanned to identify the locked pairs, naked pairs(triples also), Hidden pairs etc. and appropriately deleted. The steps 1 & 2 are repeated to fill-up the grid.
3. There exists some very hard sudokus which cannot be solved by the above methods. When no more cell could be filled up by the above steps the program jumps to a hard function which assumes one of the enumerated values and proceeds by above way. If contradictory solution is obtained then the assumed value is changed and proceeded again. This does not amount to much time since usually there are only two possible values in the cell to be assumed. Anyway, for safety, we terminate the program with an "Unable to solve" message when the solution is not obtained even after assumption of a third value.

As far as we have tested, this program solved all the sudokus, including an empty grid. I finished it by the middle of first year itself. But i didn't have a web page or blog to host it then. And now i forgot many intricate details of the algorithm. :( I re-read it once more to write this post. ;-)

This is essentially what humans do while solving. This type of algorithm has some advantages too. according to wikipedia:

human-style solvers can be employed by hand-crafting puzzlesmiths for their ability to rate the difficulty of a created puzzle and show the actual solving process their target audience can be expected to follow.

To enable this we have a function called ibug which, when enabled(at compile time) displays step by step procedure and the enumerated values at each step. It was originally written to track bugs in the code. Hence the name ;)

To know how to solve the sudoku and the terminologies used you may go here.