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 reply to Re: Pentominos Solver by Anonymous Monk
in thread Pentominos Solver by Lexicon

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.