Hexagonal puzzles, dynamic programming and polyominos.

I don't know why, but it seems that dynamic programming is not a popular technique among programmers.

In example, a couple of months ago, Carl Mäsak, an active member of the Perl and specially Perl 6 community, blogged about some puzzle played on an hexagonal grid and how to count the number of ways it could be filled with pieces of length two.

His approach was considering it an exact cover problem and using the dancing links algorithm to solve it. But exact cover is a NP-complete program, so even for the small board with 38 positions, Carl program took two weeks to complete.

Using dynamic programming this problem can be solved in a few milliseconds. I posted how to do it in Perl here. Then, Carl made an accurate and complete analysis of my script.

I keep playing with the script, modifying it to solve polyomino problems. For instance, the current version tries to complete a 12x12 grid using pentominos.

It's interesting to see how the number of parallel combinations that need to be examined explodes. In practice that means that the memory required also explodes. After all, dynamic programming is not a panacea and NP-complete problems are still hard.

A light and rough analysis makes me thing that dynamic programming transforms those 2D problems from the O(e^N) complexity and O(N) memory usage of the depth-first search approach into O(e^N1/2) complexity and O(e^N1/2) memory usage.


This question posted on PerlMonks a couple of years ago, can also be solved using the dynamic programming technique (I did it). What surprises me the most, is that nobody else tried to use that technique; and the thing is that the most brilliant minds in PerlMonks got hooked into that question!