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 | |

-------------------------

## No comments:

## Post a Comment