[geeks] Pentomino puzzle

[Phil Stracchino]

On 10/27/13 21:09, Mouse wrote:
> 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?

Sounds like a problem made for quantum computing.  ;)


-- 
  Phil Stracchino
  Babylon Communications
  phils at caerllewys.net
  phil at co.ordinate.org
  Landline: 603.293.8485