[geeks] Pentomino puzzle

[Nick B]

EC2 (or your choice or replacements) and a few hundreds of dollars of time?
Nick


On Sun, Oct 27, 2013 at 9:09 PM, Mouse <mouse at rodents-montreal.org> wrote:

> 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
> _______________________________________________
> GEEKS:  http://www.sunhelp.org/mailman/listinfo/geeks