ajy@cel (Andrew Yeomans) (10/11/90)
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. -- Andrew Yeomans, Crosfield Electronics, Hemel Hempstead, Herts, England. ajy@cel.uucp or ajy@cel.co.uk or +44-442 230000 x 3371
rickert@mp.cs.niu.edu (Neil Rickert) (10/12/90)
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
scavo@cs.uoregon.edu (Tom Scavo) (10/12/90)
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!). Here's an interesting problem along these lines. Does there exist a two-dimensional geometric analogue to 1^2 + 2^2 + 3^2 + ... + 24^2 = 70^2 ? In other words, using 24 square puzzle pieces of increasing size, can they be fit together to form one large square, 70 units on each side? I haven't the faintest idea if this can actually be done. Saw it in a magazine a long time ago. -- Tom Scavo <scavo@cs.uoregon.edu> ---------
hwb@texnix.stgt.sub.org (Harald Boegeholz) (10/14/90)
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)
manny@wet.UUCP (manny juan) (10/18/90)
Summary: Expires: References: <6596@suns4.cel.co.uk> Sender: Reply-To: manny@wet.UUCP (manny juan) Followup-To: Distribution: Organization: Wetware Diversions, San Francisco Keywords: i've written a pentomino solver (and interactive player) for the ibm pc and i've submitted it to comp.ibm.binaries.cd several weeks ago but it seems like things are slow. i'm hesitant to post the UUE file in other boards because i'm not sure if that's even allowed. i've tried sending the file to the originator of this message but my mail got returned. if anybody has suggestions or is interested in receiving the file through email, i'm willing to send it - although i'd prefer to post it somewhere. here's a bit of warning though - i haven't had much luck with elm's R-eply option. it seems that most of the replies i make are returned because of something akin to "address not found" - manny juan