Sudoku

Sudoku has become the buzz word around. Small or big, everyone seems to have been enchanted by this apparently simple number game. Like most of us, I stumbled upon this game a few days back in the Times, and have become its avid fan ever since. The only game that had driven me nuts like this before was the Rubik's cube! Basically of Japanese origin (or is it US!) the aim of the game is pretty straight forward. You have to arrange numbers from 1 - 9 in a 9 x 9 sqaure such that each number appears exactly once in every row, column and every 3 x 3 block. [Something similar to Euler's magic quare but not quite same]. It involves no luck, no math, but sheer logic, and there lies the beauty of this game.

Solving it requires patience, and with practice one can crack it in a few minutes. Well, to be frank it's not just the matter of practice, but about applying your mind, and learning with every game - a neat test of your logical skills. Try it out right away - http://www.sudoku.com/ - and you would know what I mean!

For all those programmers out there, this could be a challenging coding problem. Simple as it might seem, this in fact belongs to one of the tuffest class of problems. By that I don't mean that it cannot be solved, but just that it might not be solvable in polynomial time, so to speak. Those with a little background in algorithmics would have guessed that it has non-polynomial complexity. It is actually NP-complete and thus belongs to the league of Knapsack, graph coloring and 8-queens problem! A trivial approach to it would of course be the good old backtracking! Starting with the first blank sqaure, fill it up with a 1, move on to the next blank... continue in a similar fashion, until you break one of the constraints. As soon as you do, backtrack and fill up the last sqaure with the next possible number. Wait for a sufficiently long time and you will eventually have a solution for sure.

There are better approaches. Every blank sqaure can be associated with a list of possible values. This list will be finite and could be set to the universal set [1-9 here] to start with. Now scan the matrix, apply the contraints to each row, column and 3 x 3 block and keep reducing the set of possible values for each blank square until you are left with just one value. This approach would require many scans and updates to the lists before we have a solution. However it can be made faster if we carefully observe the pain points. Those of you who have solved a few sudoku's would be able to relate this approach to how a human mind would solve it. Note how you scan the matrix and you would soon realize that if you scan it for maximally occuring number, the count of subsequent scans would be less. In other words, if you store the frequency of occurence of numbers (currently on board), and scan the matrix for the number with max. frequency, not only would the updates be less, but so would be the required scans. I believe that applying backtracking for sufficiently small sizes of the lists would also be faster. This is so, as we would be saving on the time spent on scanning. Note also, that there's a significant time spent searching for blank squares. This could easily be eliminated by storing references to the neighboring blank squares!

It might interest you that this problem belongs to a class of problems called the Exact Cover problem. Knuth gives an elegant algorithm (which he calls the X algorithm) and an equally elegant implementation approach called Dancing Links (so called because of the way in which the doubly linked lists change links as the solution proceeds). For details, here's Knuth's paper on the Dancing Links solution - http://xxx.lanl.gov/PS_cache/cs/pdf/0011/0011047.pdf
It's implementation in java can be found in this Sudoku solver.

Keep Sudoking!
-Ashish.