good chemistry is complicated, and a little bit messy -LW |
|
PerlMonks |
Re: Pentominos Solverby Anonymous Monk |
on Jan 21, 2003 at 15:10 UTC ( [id://228700]=note: print w/replies, xml ) | Need Help?? |
I wrote one in Pascal in 1986. It took four CPU-*months* on an 80286 to run through the whole solution set. I had to make the program resumable and ran it on any unused IBM AT I could find.
The normal form is to put all TWELVE pieces into a known 60-unit shape. For a 6x10 rectangle area, there are 2339 unique solutions (with symmetric equivalents filtered out). For a 3x20 rectangle, there are TWO solutions. There are two optimizations of note. (1) Since there are twelve pieces, and you only want solutions that are unique (with symmetries filtered out), then lock one of the pieces into a single quadrant of the table. If the X-shaped piece stays in the upper left quadrant, then you won't get any equivalent solutions with the whole board flipped horizontally or vertically. (2) After you place a piece, look for any neighboring empty spaces. For each neighboring empty space, count the contiguously connected empty spaces. If any such space is not divisible by five, then you know you'll fail to put all the remaining pieces. Abort the current piece/position and move on.
In Section
Cool Uses for Perl
|
|