• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Pentominoes

 
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.)
 
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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?
 
Ranch Hand
Posts: 89
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
 
reply
    Bookmark Topic Watch Topic
  • New Topic