Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!ira.uka.de!smurf!nadia!texnix!hwb
From: hwb@texnix.stgt.sub.org (Harald Boegeholz)
Newsgroups: comp.sources.wanted
Subject: Re: Wanted - pentomino/soma cube/etc solver
Summary: I have one for MS-DOS
Keywords: pentomino soma puzzle
Message-ID: <51686.901014@texnix.stgt.sub.org>
Date: 14 Oct 90 14:40:21 GMT
Reply-To: hwb@texnix.stgt.sub.org
Distribution: comp
Lines: 40

Hi!

In article <6596@suns4.cel.co.uk> ajy@cel (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)?
Yes, some time ago I wrote a program which does exactly that.

> 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!).
This rather accurately describes what I did.

My program takes two plain ASCII files as input to describe the
parts and the shape to be filled. Both can be 3-dimensional.
It then outputs all possible solutions (if you let it run long enough) 
into a third file. The soma cube is solved in a few seconds; putting
all 12 pentominos into a 3x4x5 block takes a few minutes on a 10MHz 80286.
A second program reads this file and displays the solution graphically 
on a VGA.

The program was written under MS-DOS. The solver consists of a
10KByte C-Module (Microsoft C) and a 5KByte Assembler-Module (source).
The program to display the solution is a 12KByte C-Module. I doubt
that these programs are useful for very many people, so posting them
might not be appropriate. I can EMail the sources if you like.

This is, however, mostly uncommented code. The display program uses a graphics
library by a friend of mine, which I cannot include as source code.
Even the LIB-File is rather large (>200K), since it contains a lot of
other routines. I might go through the pain of extracting the necessary
modules, but I'd rather not do that, but send the executable instead.

One last word: I don't usually read comp.sources.wanted; the article
reached me through sci.math.

Hope this is of interest :-)

--
Harald Boegeholz    (hwb@texnix.stgt.sub.org)