Thursday, January 19, 2006

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.

Wednesday, January 18, 2006

Escape Analysis

The idea of implementing Escape Analysis in Mustang (J2SE 6) seems to be an impressive bet and finds a mention in this developerworks article -
http://www-128.ibm.com/developerworks/java/library/j-jtp09275.html?ca=dgr-jw22JavaUrbanLegends
Escape analysis refers to the analysis done on a program to determine those dynamically allocated objects and their references that "escape" or are likely to escape the method or thread scope. This has many applications with potential implications on the program performance. The knowledge of objects being bound by the method scope opens up the possibility of allocating them in the method stack frame rather than on the heap as is typically done for any dynamically allocated objects. Dynamic memory allocation (& deallocation) comes at a price. It comes with the associated problems of fragmentation, data locality and overcoming these is costly both in terms of time and space. Talking within the Java perspective, the garbage collector takes care of reclaiming the dead object space, but even the most recent generational copying collectors can "stop-the-world" for significant amount of time. Stack allocation is not only free of these idiosyncrasies but also the deallocation happens implicitly on method return. Moreover, better data locality means that there would be less cache misses.

Knowledge of local objects also gives the compiler/optimizer a chance to get rid of the object altogether in some cases. The link above has a code snippet justifying the same.

If an object does not escape the thread, the overhead associated with its synchronization can be eliminated. This is significant because forgetting to synchronize objects being accessed by multiple threads can pose serious issues like race condition, spurious and unexpected results etc. Compilers and optimizers often reorder instructions for efficient execution. While this is acceptable in a typical sequential execution, this might cause unexpected results in a multithreaded multiprocessor environment. To add to this, the java memory model does little to ensure the data atomicity, visibility and ordering in such cases. And it is not to blame... with new environments coming up every other day, it is next to impossible to ensure correct execution. Needless to say, thread local objects are desirable and anything that can be done to identify them in a multi threaded program is worth the effort.

Okay, so escape analysis seems to be desirable. How do we go about implementing it? The short answer could be - Do it however you like! :)
Basically, what this would require is an understanding of the relationship between the various dynamically allocated objects and references... something similar to what a compiler would do in the dataflow analysis. We need to track the object right from it's inception to how it is accessed in a method to how it gets passed to other methods to whether it would be accessed by other threads until it is reclaimed by GC. There are ample articles to peruse varying in details on escape analysis in general, it's application in Java and various implementation strategies. Here's a pointer -
http://citeseer.ist.psu.edu/choi99escape.html

Whether or not escape analysis is implemented in Mustang is still being debated and you will find many forums dedicated to this topic. But then nothing stops us from delving into the code and contributing to the build!

Happy Coding :)
- Ashish.