Perl: the Markov chain saw  
PerlMonks 
Comment on 
( #3333=superdoc: print w/ replies, xml )  Need Help?? 
Sounds like a case for Branch and Bound. I would partition the problem space by adding the next free category to either last used column or the next empty column. The root problem would be "category 1 in column 1", so the children would "category 2 in column 1" and "category 2 in column 2", etc. The low boundary for each solution is the height of the highest column, and the solution's high boundary is maximum(sum of heights of free categories, lower boundary). There is a constraint (free categories > empty columns) that has to be fulfilled to assure there will not be empty columns. It's probably best to generate the solution tree breadthfirst as you will descend far down the left side very quickly if the global lower and upper boundaries have not been narrowed down. Breadthfirst would garantuee that you limit them soon. On the other hand, for larger problems the breadthfirst approach will also require more memory to hold the solution tree. I tried to write code yesterday but it was 3am and my mind wouldn't cooperate. Now I've just gotten up way waay too late into the day and it still doesn't. Makeshifts last the longest. In reply to Re: Puzzle: need a more general algorithm
by Aristotle

