Xref: utzoo sci.math:6581 comp.lang.prolog:1706 comp.ai:4044
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!lll-lcc!lll-winken!uunet!mcvax!ukc!etive!epistemi!edai!cam
From: cam@edai.ed.ac.uk (Chris Malcolm    cam@uk.ac.ed.edai   031 667 1011 x2550)
Newsgroups: sci.math,comp.lang.prolog,comp.ai
Subject: solving soma puzzles
Summary: Have computer solution, want faster.
Keywords: soma, pentominoes, combinatorial explosion
Message-ID: <336@edai.ed.ac.uk>
Date: 29 Apr 89 15:22:18 GMT
Reply-To: cam@edai.ed.ac.uk (Chris Malcolm)
Organization: Dept. of AI, Univ. of Edinburgh, UK
Lines: 60

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