cam@edai.ed.ac.uk (Chris Malcolm cam@uk.ac.ed.edai 031 667 1011 x2550) (04/29/89)
I need fast methods of solving this kind of problem in a computer - I have a PROLOG program which does it, too slowly. [It is methods I'm interested in, not the relative virtues of programming languages]. The soma4 set of parts consists of one of each shape which can be made from 4 or less cubies (small cubes) of the same size stuck together face to face, to form an irregular shape, i.e., which has a concavity. There is only one consisting of 3 cubies, and 6 consisting of 4 cubies, = 27 cubies in total. There are 240 distinctly different ways of constructing a 3x3x3 cube out of these parts. This is the original Soma puzzle, invented by Piet Hin. Martin Gardner in Scientific American, and in "More Mathematical Puzzles and Diversions", and Berlekamp, Conway, and Guy, in "Winning Ways", have discussed this puzzle. I am interested in a generalisation of this puzzle: using soma5 (made from 5 or less cubies), soma6, etc., parts, discover how to build (or whether it is possible to build) arbitary shapes - walls, towers, elephants, etc.. I have a PROLOG system which does this, but tediously - it can sometimes take hours. It simply tries all possible combinations of all possible translations and rotations of the parts in the shape until it finds one which fits. I am therefore interested in GENERAL methods of cutting down the size of this search space, which can be applied to ANY shape made from ANY set of these kinds of parts. Pentominoes are a 2D subset of the soma5 problem. I am aware of the chequering system mentioned by the above authors. My system also checks that the sizes of all holes left in the assembly can be filled by the remaining set of parts, e.g., using the soma4 part set, one can fill a hole of size 8, or 2 holes of size 4, but not 2 holes of size 5 and 3. These methods multiply the speed of solution a few to several times each. But I want an improvement of a few to several orders of magnitude. I have heard a rumour that there exists a generalisation of the black/white chequering system to multiple colours, which enables solutions to be be derived very rapidly indeed, but have been unable to re-invent it - if indeed it exists. The nice thing about chequering a shape is that it is rotation-invariant - given that the only rotations of interest are rectangular rotations about the natural axes. Also of interest are ways of biassing the search order towards solution-rich areas, such as selecting the next part/position to try on the basis of greatest reduction in surface area of the shape to be filled - i.e., fill the spiky bits first. There is an interesting general problem behind this specific problem, which I hope solving this specific problem may provide some clues for. Computer systems which reason about operations on 3D shapes (modellers, assembly planners, mechanical designers, etc.) require gross amounts of computational horsepower to tackle realistic problems. Like early chess programs, their failing is that they consider the whole problem at its atomic level of detail. Are there any abstractions from this kind of problem (e.g., projection onto 3 orthogonal planes) which could be used as the basis for computationally _much_ cheaper, probably hierarchical, geometric reasoning systems? -- Chris Malcolm cam@uk.ac.ed.edai 031 667 1011 x2550 Department of Artificial Intelligence, Edinburgh University 5 Forrest Hill, Edinburgh, EH1 2QL, UK
prem@crackle.amd.com (Prem Sobel) (05/03/89)
In article <336@edai.ed.ac.uk> cam@edai.ed.ac.uk (Chris Malcolm) writes: >I need fast methods of solving this kind of problem in a computer - I >have a PROLOG program which does it, too slowly. [It is methods I'm >interested in, not the relative virtues of programming languages]. At work some one had a 3x4x5 puzzle with 12 pieces of 5 cubies each. I started to solve this by hand but it took me hours to get the first solution. When I was told that there are 3940 solutions it was time for a computer program. It turns out that the pieces in this puzzle took the restriction that one dimension of the three would always be one cubie thick. The first approach was brute force: 12 pieces 24 orientations 60 positions which is: (24*60)^12 combinations to try. This, takes much too long so had to add some more intelligence to the program. The first step was add logic which removed symmetries from the piece. For example the piece: ## # ## has one axis of symmetry cutting the 24 orientations to 12, while the piece: # ### # has full symmetry and has only 3 orientations to try. This was still not enough. The next step, observing how I solved the puzzle, was to add logic to prune the search tree to eliminate placements which create remaining holes either too small or unable to take any of the remaining pieces. Any further, improvements to the program seemed to slow it down so I stooped there. At this point it takes a SUN-4 28 minutes to get the first solution and a 29000 with slow memory about 7 minutes. If anyone is interested I can email them the program, it is fairly large and is not the most commented C progarm I ever wrote, but it is bug free :) By the way, it read a file which gives the shape descriptions. It is easy to extend the program to change the size of the puzzle. It is slightly harder but not very to generalize it to take pieces which are not unit thickness in one dimension. Prem
holey@umn-cs.CS.UMN.EDU (J. Andrew Holey) (05/04/89)
When I was an undergrad in mathematics (several years ago), I was doing some investigations into perfect numbers. I received a soma cube as a gift about that time, and I noted with interest that one irregular shape could be formed from three cubies and six could be formed from four cubies. To the best of my ability I determined that about 496 irregular shapes could be formed from five cubies. My conjecture was that these numbers might be somehow connected to perfect numbers. Does anyone have any better results on this matter? Andy Holey holey@umn-cs.cs.umn.edu
dsr@olduvacs.cs.Virginia.EDU (Dana S. Richards) (05/08/89)
In article <336@edai.ed.ac.uk> cam@edai.ed.ac.uk (Chris Malcolm) writes: >I need fast methods of solving this kind of problem in a computer - I >have a PROLOG program which does it, too slowly. [It is methods I'm >interested in, not the relative virtues of programming languages]. > I am therefore interested in GENERAL >methods of cutting down the size of this search space, which can be >applied to ANY shape made from ANY set of these kinds of parts. > >Pentominoes are a 2D subset of the soma5 problem. > Some references from my files (mostly for pentomines): Comm ACM 18(1975)651-656. Math Spectrum 8(1976)39-50. Comm ACM 8(1965)621-623. Byte (nov 1979)26-52. and an interesting item of little value today, Dana Scott, "Programming a combinatorial puzzle", tech rept princeton 1958. I did some unpublished work many years ago but have forgotten how it went. dana richards
grover@potomac.ads.com (Mark D. Grover) (05/12/89)
In article <3124@olduvacs.cs.Virginia.EDU>, dsr@olduvacs.cs.Virginia.EDU (Dana S. Richards) writes: > In article <336@edai.ed.ac.uk> cam@edai.ed.ac.uk (Chris Malcolm) writes: > > > I am therefore interested in GENERAL > >methods of cutting down the size of this search space,... > > I did some unpublished work many years ago but have forgotten how it went. This is sort of interesting. My senior undergraduate project back in 1975 attacked Soma using A* and a silly heuristic. I remember how it went: poorly. I wonder how many other folks have picked Soma or similar spatial puzzles as initial problems. - MDG - -- Mark D. Grover (grover@Potomac.ADS.COM) Advanced Decision Systems 1500 Wilson Blvd #512; Arlington, VA 22209 703-243-1611 "Back off, man. I'm a scientist."