Saturday, March 28, 2009

It's Possible...!

Kudoz to professor emeritus James F. Crook for having devised an algorithm for solving Sudoku puzzles. Here are some quick pointers about his "Pencil-and-Paper Algorithm":

• The algorithm is made up of five logical steps
• It requires players to mark up empty boxes in the Sudoku grid with all possible remaining number and, by comparing number sets, to labour through a "tree" of options that ultimately provides a solution.
• As of now, the computer takes takes over an hour to solve a Sudoku puzzle. (See humans always outsmart computers ;))
• The paper text can be viewed here.

This algorithm is certainly an achievement in the mathematical world and reinforces the fact that almost everything that can be depicted as a flowchart is solvable by computers. After all computers have been known to be super efficient in deconstructing seemingly tough problems and hammering out their solutions using computing power!

What puzzles me though is how come human beings are able to solve a difficult Sudoku in just 10-15 minutes time while this latest algorithm takes an hour to crack a Sudoku puzzle? Is it our logic sense or intuition or just our imagination that does the magic-Well, I don't know! What I do know is the fact that struggling with my pencil (I don't mean chewing the back of the pencil over and over again ;)) and working out a Sudoku puzzle on a Sunday morning is an adventure in itself. And the "Ahaaa" feeling (emotional high) you get post solving a puzzle keeps the excitement and the desire to solve the next puzzle on :D

Happy weekend folks and good luck for today's puzzle!
"A moment's thinking is an hour in words."~ Thomas Hood

Dhruva said...

Hmm! I am sure you dont need me to tell you :) , and you already know, that the reason computer is taking so long is because it is making "random guesses" and it is not actually "solving the puzzle".

I am sure a better algorithm will come in coming years, which will rather try to solve it, hence will do faster. (i guess something on line of AI)

This also reminds me of two common methods of attacking/hacking a passwd - dictionary method vs Brute Force method. Dictionary method works fast as less permutations/combinations, however brute force takes longer as it tries all combinations.

http://en.wikipedia.org/wiki/Brute_force_attack

http://en.wikipedia.org/wiki/Dictionary_attack

Anonymous said...

The Paper and Pencil -- the fantastic power in this world that has been the grassroot of so many innovations by mankind till date and believe me , I just stumbled upon my desk when I read about the paper and pencil algo and the first thing that clicked my mind was that -- not again , the paper and pencil even captured sudoku ! Well written, hope to catch up with more innovative posts like this...

s k gupta said...

very nice blog.