Thursday, March 08, 2007

Sudoku Solver

It is very unlikely for me to post twice in a day, yet I am back again. I had a little idle time at my disposal so I thought to put it to some use.

A couple of months back I read in Times of India about world Sudoku championship which was to happen in March 2007. In addition to the day to day sudoku puzzles they included certain variation of the puzzle too, to encourage readers to take part as well as to stimulate their brain :D.

Sudoku took over my mind during those days and I was completely engrossed in reading about Sudoku as well as solving them at websudoku . It occurred to me why not write a program to solving the puzzle? So I took up the task and was ready with a small Sudoku Solver .

Of course, for certain inputs it does not give the solution. I pondered over the completeness and soundness issues of the initial sudoku board. I don't know whether it is appropriate to use these terms which are often used and associated with algorithms. Let me define it this way. Completeness means that the initial information given in the board should be sufficient to solve the puzzle by using only inferences ( No guessing game/No coin tossing/ No breaking tie). In other words, there must exist at most one solution that can be derived from the initial configuration of the board. Soundness means that the information should not be conflicting, or say, at least one solution exist that can be derived from the initial information. I discussed the matter with my mathematics teacher Mr Motilal Panigrahi at GCET .

We could not arrive at any definitive proofs or conditions to ensure the soundness and completeness, but it was nice to chat with him over these things years after I left the college.

Sherlock Holmes

Lately, I have been reading famous "Sherlock Holmes" stories. What a nice piece of literature it is! Sir Arthur Conan Doyle is truly a master of creating writings that hold the reader till the end. It really takes a true genius to create such a timeless character like Sherlock Holmes.

Though, some of the inferences employed by Sherlock Holmes in unleashing the truth seems to be unrealistic, I especially admire the literature for the flair with which the author wrote it. The description of a scene creates enough impact on your mind to force it to weave a virtual world around as if you are witnessing the entire series of events. Author has put to use his vocabulary so perfectly that it does not drive away a reader with average vocabulary and yet maintaining enough variations to make it far from banal. I wish I could attain at least 1/20th of author's writing skill.

Now I know, why Sir Arthur Conan Doyle was awarded knighthood. :-)