Path: utzoo!attcan!uunet!dino!ux1.cso.uiuc.edu!mp.cs.niu.edu!rickert
From: rickert@mp.cs.niu.edu (Neil Rickert)
Newsgroups: comp.sources.wanted
Subject: Re: Wanted - pentomino/soma cube/etc solver
Message-ID: <1990Oct11.220149.28479@mp.cs.niu.edu>
Date: 11 Oct 90 22:01:49 GMT
References: <6596@suns4.cel.co.uk>
Organization: Northern Illinois University
Lines: 28

In article <6596@suns4.cel.co.uk> ajy@cel.uucp (Andrew Yeomans) writes:
>Does anyone have a program to solve problems such as pentominos, n-tominos,
>soma cube, etc, where irregular shaped blocks have to be packed into a
>larger cube (or other shape)?
>
>It shouldn't be difficult to write one (map 3 dimensional shapes to 1-D bit
>arrays, then use bit operations to test which pieces fit, add some
>recursion and maybe some heuristic speedups and there you have it!).
>However, I'd rather not re-invent the wheel.

  I did this many years ago for pentominos.  I wrote the program in assembler,
and did as much work in registers as possible to get super fast performance.
I then let the program run for 20 minutes of CPU time, and took a memory dump
to see how far it had got.  It turned out that the program had worked perfectly,
doing the test just as I had expected.  The trouble was it spent the full 20
minutes trying to insert the pieces somewhere where any two year old could
tell you they wouldn't fit.  I finished up with a much more complex
algorithm which, after placing a piece, found the connected components of
the space that was left, and made sure that every connected component had
size a multiple of 5.  The program was a mess, but it started grinding out
answers at a reasonable rate.

  Moral.  The obvious approach is doomed to failure.
-- 
=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
  Neil W. Rickert, Computer Science               <rickert@cs.niu.edu>
  Northern Illinois Univ.
  DeKalb, IL 60115.                                  +1-815-753-6940