[geeks] Pentomino puzzle

[Mouse]

I assume everyone here knows what pentominoes are.  (Well, actually,
no, I don't.  But everyone who is likely to find the question I'm about
to ask interesting probably does.  For the two people who find this
interesting but don't yet know them, see the Wikipedia page
"Pentomino".)

The question: what 60-square shape, treated as a pentomino puzzle
(piece reflection allowed), has the most solutions?

The 6x10 rectangle has 9356, or 2339 after reducing for symmetry of the
shape.  But this is easily beat by the 8x8 square with one 2x2 corner
removed, which has 10054, or 5027 after symmetry reduction.  It's
possible to do better (I looked at some 7x9 rectangles with three
squares removed and one of them has over thirteen thousand solutions)
and I'm wondering if anything has been proven best.

In theory, it's a trivial problem: just generate all 60-ominoes and try
them.  But that'd be insanely expensive; my rough estimate is that
there are on the order of 10^34 60-ominoes.  Just enumerating them all,
never mind actually doing anything significant with each one, is out of
reach.  It would be a smaller enumeration exercise to run through all
possible ways of forming a connected shape with the pentominoes.  I'm
doing this right now with the factor-of-2 magnification of the
15-ominoes; the run just to generate the list of 15-ominoes took over a
week (there are 3426576 of them).  This is probably in large part
because the program uses O(n^2) algorithms heavily - but even speeding
it up by 10 orders of magnitude would still leave the problem
hopelessly out of reach.

Any pointers?  Or other thoughts?

/~\ The ASCII				  Mouse
\ / Ribbon Campaign
 X  Against HTML		mouse at rodents-montreal.org
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B