Quite a while (and a half-dozen jobs) ago, I wrote program to solve pentomino problems. It was VERY brute force. It was a bunch of nested for loops that cycled through x and y coordinates and various rotations/reflections for each piece. Given the algorithm and the available hardware, it took over an hour to solve the twelve "3x" problems.* With just a little tweaking of the initianl data, it also solved the problem of fitting them all in a 5x12 or 6x10 rectangle.
Surely there's got to be a better way than brute force. Any thoughts?
(The 3x Problems: Select one of the twelve pieces, and use 9 of the remaining 11 pieces to make a 3x scaled version of the one you selected.)
That second page has an applet that allows you try to place the twelve five-square pieces in a 6x10 grid. That's just one possible puzzle. There is another set of puzzles with the same pieces where you select one of the twelve pieces and then try to make a triple sized version of that pieces with nine of the remaining eleven pieces. For instance, if you select the piece that is 1x5 pieces long, then you'll be trying to use nine OTHER pieces to fill a 3x15 rectangle.
Like I said, I solved these puzzles once using a very inefficient brute forrce alorithm. Is there a better way?
How about this for an algorithm? It's impossible to get away from brute force, but the big thing is to trim the tree of possibilities as early as possible:
By calculating the count at the start, you automatically avoid dead ends as soon as they occur (the brute-force method tends to only throw its hands up at the end - ie. if it puts the cross-pentomino is a corner, it'll still try every combination thereafter!), and automatically zero in on the limiting factors
[ June 20, 2006: Message edited by: Rob Acraman ] [ June 20, 2006: Message edited by: Rob Acraman ]