Taming the Sudoku

Step 1: The Deterministic Sudoku

Dear readers,

After a few days of relative unproductivity, I tried my hands on a disjoint problem hoping to see/sense a revival of interest in my thesis writing endeavour. I picked up Sudoku.

I am not an avid Sudoku lover neither do I intend to be one. Whenever I went home, I often found my father immersed in The Telegraph - t2's Sudoku page. He did a lot of guesswork. I always pointed out that it could be solved using simple elimination, substitution methodology. Little did I know that Sudoku was actually a nondeterministic (ND) problem*.

Yesterday, I wrote a nifty solver for solving Sudoku. It is efficient and runs pretty fast. However, it only works for deterministic Sudokus - ones that are labelled Easy and Moderate by the newspapers/magazines. (I did not even know they were supposed to be ND as well).

Attached:
http://sauvik.prcxyz.com/data/sudoku_solver.zip

The zip file also contains some input files that are downright 'evil'. The solver could only solve two cells of the 'extreme' grid. The corresponding output is piped to *_out.txt

You'll have to compile the source 'sudoku_solver.c' yourself. Open this file in a text editor to read the instructions**.

Most sources that can solve ND Sudokus are very slow. I'll have to read a bit to mod this and make a fast ND solver for such Sudokus. I may not be even working on them for a very long time. There may not be even a step 2. My thesis is my priority.

Regards.

*For all the purists, I am not calling upon the complexity clause and putting a "polynomial time" suffix to it. I know of it's NP nature, but at this point I am least bothered about an optimised solution algorithm.

**Copying the instructions from the file:

Compile this program using the following syntax
 gcc sudoku_solver.c -o sudoku_solver.out
Run it using the following command
 ./sudoku_solver.out <input_filename>

The contents of the input file must be of the form
 0    0    0    8    0    0    5    0    2
 6    0    9    0    3    0    4    1    0
 3    8    5    4    0    0    0    0    6
 0    0    0    2    0    0    1    5    9
 0    6    0    0    0    0    0    2    0
 9    1    2    0    0    3    0    0    0
 2    0    0    0    0    8    9    7    5
 0    5    4    0    9    0    8    0    1
 8    0    1    0    0    5    0    0    0
to represent the following unsolved Sudoku
 -------------------------
 |       | 8     | 5   2 |
 | 6   9 |   3   | 4 1   |
 | 3 8 5 | 4     |     6 |
 -------------------------
 |       | 2     | 1 5 9 |
 |   6   |       |   2   |
 | 9 1 2 |     3 |       |
 -------------------------
 | 2     |     8 | 9 7 5 |
 |   5 4 |   9   | 8   1 |
 | 8   1 |     5 |       |
 -------------------------