File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Programming Diversions and the fly likes Pentominoes Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Pentominoes" Watch "Pentominoes" New topic
Author

Pentominoes

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1007
    
    3
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.)
Amod Bhatia
Greenhorn

Joined: Jun 04, 2006
Posts: 10
I didn't get your question at all !!
kindly any body please tell me the whole scenerio in easy words to have more exitement while solving problem !!
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1007
    
    3
Originally posted by Amod Bhatia:
I didn't get your question at all !!
kindly any body please tell me the whole scenerio in easy words to have more exitement while solving problem !!


Try this page or this page for an explanation of pentominoes.

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?
Rob Acraman
Ranch Hand

Joined: Dec 03, 2000
Posts: 89
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 ]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Pentominoes