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.

Friends' Blogs

Vasanth, my senior, friend and guru in management, started a blog almost at the same time as me and is rocking after going to NITIE.

I went to the battle field armed with full hand buttoned, tucked in shirt and formal leather shoes (at 3.15 am) and tasted victory in all the 3 battles.

He is actually describing his interview. By the way, he has a nice template too...
Note to Vasanth: I'm gonna steal your template soon(With a fighter in the place of car, of course.)

Recently I found the blog by my friend B aka Stranger. The blog is hilarious to the core. I guarantee that you'll laugh and laugh till your co-workers(or students) wonder what the hell happened to you. An excerpt:

BS: Is Today your BCM?
JP(Confused): No! Why do you think so?
BS: You look smart only on your BCM days.. He He He
(Loved that smile on his face)

Paavam co-workers...

UPDATE: Vasanth changed his template. But this too has a car.

கணிமொழியின் ஆடி மாத இதழ்

கணிமொழியின் ஆடி மாத இதழ் வெளியாகியுள்ளது.

"ஆடியிலும் உங்களைப் பிரியாத கணிமொழி"
--ஆமாச்சு.

படித்து பயன் பெறுக.

UPDATE:
For those who don't have Tamil Unicode font: Kanimozhi is a monthly magazine about the free softwares(GNU/Linux etc) and and contains tips & tricks to use them. Go here and follow the steps to install Tamil Unicode fonts and enjoy reading the July edition.

QOTD In Aero

In theory, there is no difference between theory and practice. But, in practice, there is.

-- Jan L. A. van de Snepscheut

Saw this in our textbook(Jet Engine, Rolls Royce). Especially true in Aeronautical Engineering.

Wordpress Programmers Are Smart Enough To Display Your Passwords In Cleartext

I may not be the best programmer, but I' know programming well enough not to mail the password in cleartext or display your password in an unencrypted web page.

The password I received in mail or the one shown in the web page is not auto generated. It is MY password in clear text.
Idiots.

On a related one see this by Jeff Atwood.

Indian Media is a Ring Circus

I'm amused at the prank played on Indian media.

Kudos to Pen Pricks

ROFTL :)