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

Dasavatharam

Plain nonsense.
I went to movie, despite bad reviews, hoping it would at least be watchable once.
Result: Severe headache.
No comment about kamal roles. Asin is irritating at best. Why the hell does he write screenplay when he is not capable of even a semi-decent one?

Someone wrote "People whoever written good about the movie are talking more about Kamal and whoever written bad about the movie are talking more about the Movie itself." I see a film for its story and screenplay. I don`t give a damn if Kamal dons 10 characters or works hard to act as an old lady.

P.S.: I want my money back.

OOXML On Hold

Due to protests from South Africa, Brazil, India and Venezuela, ISO put on hold the OOXML standardization process two days ago.

The OOXML format is not fit for anything, let alone an international standard. It is full of bugs(sample), non compatible with itself(!?, forget ISO/IEC compliance) and more. It is carefully designed to enable only MS to build applications that can handle the said format. It is a move to monopolize the market and is against public interests.

Microsoft heavily influenced the standardization process with all the means one could imagine. It even lodged complaints against BIS committee members that they are acting against national interests.(Apparently, to Bill Gates, national interests means Microsoft's interests.)

Here is an open letter protesting that, by Prof Deepak B Phatak, IIT Bombay, India. He is one of the BIS committee members. A Tamil translation of the same(in part) can be found here.

Top 10 Life Tips

Nassim Taleb's life tips and more presented here are really useful.
The ones that caught my attention were:

5 Don’t disturb complicated systems that have been around for a very long time. We don’t understand their logic. Don’t pollute the planet. Leave it the way we found it, regardless of scientific ‘evidence’.

7 Avoid losers. If you hear someone use the words ‘impossible’, ‘never’, ‘too difficult’ too often, drop him or her from your social network. Never take ‘no’ for an answer (conversely, take most ‘yeses’ as ‘most probably’).

9 Hard work will get you a professorship or a BMW. You need both work and luck for a Booker, a Nobel or a private jet.

Hat tip to Ben.

Learning FEA. Is there an open source FEA software?

Currently I'm learning FEM(Finite Element Methods) for structural problems from my HOD. We use computers for solving those problems fast and in our lab the software used is ANSYS. I'm an ardent supporter of free software and am searching for an equivalent Final Element Analysis software in Linux. Or at least GPLed Windows software. I saw some of those using Google search. But I'm not satisfied with their capabilities.

Anybody know such good software? If so please comment.

PS: Twisted DNA suggested doing a post on 'navel bra' as my first post. But my research(;)) on that is still under progress(!). Hence I write a different first post.

Test post.

hello... blog testing 1 2 3...