Arrange pentominos in 3x20, 4x15, 5x12, 6x10, 2x3x10, 2x5x6 and 3x4x5 forms.

Additional material

[ Editor: from Matt Fichtenbaum's 1994 summary of responses about a
  wooden puzzle of 12 pentominoes to be packed into a 5x4x3 box, and a
  1995 thread on pentomino names. ]

Our exhaustive-search program stopped after finding one solution; by
symmetry, there are eight direct variations of it.  The solution it
found is

      ..8....A....6....6....6..
    ..8....5....B....6....4..
  ..8....B....B....6....4..
..B....B....4....4....4..


      ..8....A....A....A....7..
    ..5....5....5....C....7..
  ..8....3....C....C....C..
..3....3....3....3....C..


      ..9....9....9....A....7..
    ..2....5....9....9....7..
  ..2....2....2....2....7..
..1....1....1....1....1..

This solution does not appear to map directly into the single-plane
pentomino problem.  But you never know.

-- Matt Fichtenbaum <mlf@genrad.com>

[ Editor: replies on speeding up a search program follow. ]

Since you've already got the program written (and, hopefully,
debugged :-) ) there are some fairly straightforward ways of speeding
it up.  First of all, try checking if there are any positions which
there's no way of fitting an available piece into.  For example, if there's a position
which has all six faces filled in by other pieces, there's obviously no
way to fill it.

A more sophisticated technique is to figure out which position can be
fitted with a piece in the fewest possible ways, and run through all
possible ways of putting something into it.  The first technique is
really just a small piece of the second technique (if there's a
position with zero ways of getting filled, then you've checked all the
possibilities already.)

Incidentally, *every* heuristic I know of for exhaustively finding
solutions to a puzzle-type (or even non-puzzle-type) problem is based
on the same principle: find a very restrictive clause (in this case
that a position must have a piece in it) and branch on it.

From your description, it sounds like your program currently branches
on the next piece to be placed.  The simplest heuristic there is to
always place the largest remaining piece next, but it might not work in
the specific case you're working on because many of the pieces are the
same size.

The natural extension of this technique is to count how many positions
each piece can be put in and branch on the one which can be put in the
fewest.

-- bcohen@acsu.buffalo.edu

Here's one method of doing it [ Editor: the 3x4x5 ] (looking from
above throughout):

Place the X piece on the table:

    X
   XXX
    X

Now, place the U piece on top of this like so (looking from above):

   UX
   UXX
   UX

And add the Z piece:

1  UXZZ
2  UXXZ
3  UX ZZ

The three numbered rows correspond to 3 parallel planes containing the
row and perpendicular to the table.  The remaining pieces (in lots of
3) will complete these individual planes.

Planes 1 and 2:

     Y       V
  WWYY    SSSV
 WWPPY   SSVVV
 WPPPY   IIIII

Plane 3:

   F
  FFFT
 LFTTT
 LLLLT

Put them all together and you have a 3 by 4 by 5 rectangular prism.

-- ftww@staff.cs.su.oz.au

It's simply a 3-D solution of the pentomino puzzle that's been around
for years.  When you get through with the 3x4x5 puzzle you can tackle
the 3x10x2 and 5x6x2 puzzles.  It's also possible to make 3-layer
solid models of each of the pieces, all except W and X.

I too have a program that searches for planar pentomino solutions.  It
doesn't take a supercomputer, I run it on a 286/12 and it finds the
solutions to the 3x20 puzzle in 2 minutes and the 6x10 puzzle in 48
hours total run-time.

There should be more than one solution.  I think that there are
something like 3940 different solutions!

Here's a couple that I know of [ Editor: of the 3x4x5 ]:

  Layer:   1     2     3      1     2     3      1     2     3
         IIIII PPZZX TTTWW  TTTPP UTYPP UTXPW  LWWXZ WWZZZ WFZPP
         YYYYX PPZFX VTWWX  IIIII YYYYW UXXXW  LVXXX IIIII FFFPP
         NNYFU PZZFX VTWFU  FFZZW UFFZW YFXZZ  LVTXU TTTNN FYTPU
         LNNNU LLLLU VVVFU  VLLLL VNNNL VVVNN  LVVVU LNNNU YYYYU

           1     2     3      1     2     3
         NLLLL IIIII YUUUV  IIIII WNZZP WLLYP
         NLXWW YXXXP YUXUV  WUUXP WNFZP VNLYP
         NTWWP NTTTP YTVVV  WUXXX FFFZZ VNLYY
         ZZWFP NZFFP YZZFF  VUUXT VFTTT VNLYT

Here's 4 solutions to the 5x6x2 puzzle, just to prove that it's
solvable.  There are 264 possible solutions:

           1     2      1     2      1     2      1     2
         VVVFN TTTWW  PPUUU IYYYY  UUULL VVVWW  IUUUL NZVVV
         VFFFN ITWWL  PPUXU IZYLL  UXULI VTWWY  IUXUL NZZZV
         VXFNN ITWZL  PFXXX IZZZL  XXXLI VTWYY  IXXXL NNWZV
         XXXNP IZZZL  FFFXV ITWZL  PXFLI TTTZY  IFXPL TNWWL
         UXUPP IZYLL  FNNNV ITWWL  PFFFI PZZZY  IFFPP TTTWW
         UUUPP IYYYY  NNVVV TTTWW  PNNFI PZNNN  FFYPP TYYYY

-- bob.childress@greatesc.com

The box mine comes in says there are 2339 different solutions for the
planar version [ Editor: the 6x10 rectangle ].

One possible planar solution is:

77aac11111
7aacccb998
77a5cbb988
6555bb9984
6625333384
6622223444

where piece 10=a, 11=b, 12=c

-- jrl@images1.waterloo.NCR.COM

[ Editor: Bill Taylor's names and mnemonic for the pentominoes. ]

            _
           |_|     _
    _ _    |_|    |_|       _ _      _ _ _    _ _ _
  _|_|_|   |_|    |_|      |_|_|   _|_|_|_|  |_|_|_|
 |_|_|     |_|    |_|_     |_|_|  |_|_|        |_|
   |_|     |_|    |_|_|    |_|                 |_|

    F       I      L        P        S          T
                                        _
            _       _          _      _|_|    _ _
  _   _    |_|     |_|_      _|_|_   |_|_|   |_|_|
 |_|_|_|   |_|_ _  |_|_|_   |_|_|_|    |_|     |_|_
 |_|_|_|   |_|_|_|   |_|_|    |_|      |_|     |_|_|

    U         V       W        X        Y      Z

Then the mnemonic is "FLIP S to Z" (a natural geometric operation!).
In other words...  FLIP STUVWXYZ.

-- Bill Taylor (quoted by Earle Jones)

I have a copy of Polyominoes 5.0 for the Mac.  (Written by Kevin L.
Gong--it's $8.00 shareware.)  It is a well-written bug-free (?) program
with a lot of flexibility.  You can set up your own puzzles with
triominoes, tetraminoes, pentominoes (see above), etc.

-- Earle Jones <ejones@hooked.net>

[ Editor: ftww's 3x4x5 diagram and Taylor's names use S for the piece
  the archive calls N.  A 3x20 solution mailed by a TU Delft reader
  appears to be the one already in this entry and is omitted. ]

[ Editor: the 8x8 square filled with the twelve pentominoes and the
square tetromino. ]

In article <2jd1gm$61u@salmon.maths.tcd.ie> asdfghjk@maths.tcd.ie
(Nicholas Gray) writes:
 >  Can somebody confirm the rather large figure of 32292 solutions
 > to the 8x8 square filled with all the pentominoes and the square
 > tetromino? I got this with a program I wrote (it took a very long
 > time), but it does seem a bit big.

Yes, I can, in a way.  There are 10 essential different ways to put the
square tetronimo.  For those 10 ways I found the following table (in
front are the coordinates of the square tetronimo):
1,1: 5027
1,2: 3207
1,3: 1839
1,4: 1288
2,2:  987
2,3: 1662
2,4:  721
3,3:  582
3,4:  768
4,4:   65
These all count rotations, mirror reflections etc. as one.  The total
is 16146 which looks surprisingly like one half of what you had.  I
assume you counted rotations as one but mirror reflections as
different.  (It took 15 hours computing.  Of these 5 hours where spend
on the first and 7 seconds on the last.  But that is, I think, more
than was needed because of some suboptimal strategy I am going to
correct.)

Why do you think it is a bit big?  Because it is so difficult to find a
solution by hand?  Remember that there are similar puzzles that allow
billions of solutions and that are nearly impossible to do by hand.

-- Dik T. Winter <dik@cwi.nl>