Solving multiple puzzles

A fine solver 
Watch this Newsletter,
as this solver may be changing, the article may expand.
This solver is the product of Marc Moerig "marc@moerig.com"
The sensational solver will solve not only SOMA puzzles, but other sets as well.
It is an extremely nice solver, with a great user interface.
Somatic is a generic solver for arbitrary soma like puzzles. It can check whether a given figure is solvable with a given set of pieces. It does also solve partial figures, which do not need all pieces to be build. Currently it only delivers one solution.
Somatic is released under the GPL, which allows you to modify and/or redistribute it under certain conditions.
To get this wonderfull program, you should visit the homepage
http://www.moerig.com/somatic/
The program is currently version "somaticwinbinary20040318.zip"
One drawbeck though is, that the dataformat (in this version) is not the same
as all the other SOMA solvers. But there's a reason for that.
Because THIS solver can do NOTonly SOMA, but also a large range of other puzzles,
so our SOMAdataformat is not sufficient (Marc is looking into the problem though (feb 2004))
Marc says that making the same color sceme, and solution notation, as on these
SOMA web pages, is very unlikely, because it requires the program to know that
it is using a soma (somaplus, double soma, bedlam, etc) piece set, and for the
coloring also which piece it is handling.
Currently the program doesn't know that.
You are on the other hand, able to define any kind of piece set through the
input file, so making a specific notation would require the program
to "recognize" special piece sets and handle them individually. This will
not be done, because it would mess up the generality.
Currently there are only two limitations:
A piece has to be connected, that is you can reach any cube from any
other cube by walking through the sides ob the cubes. (This just means i
only consider pieces that can be crafted in reality.)
The solver does not accept figures with more than 64 cubes, the set of
pieces however may have an arbitrary number of cubes. This could easily
be extended to 128 or any arbitrary number, however the decision problem
"Given a set of pieces and a figure, can i build this figure ?"
is NPcomplete ( http://www.claymath.org/millennium/P_vs_NP/ ) so there is
no hope (unless P=NP) of solving bigger problems anyway.
It may happen though, that a module will be added that can read
the public SOMA format, so the program can profit from the huge database of
problems, and "maybe I will add a write feature too." Marc writes.
(So let's hope for both a read and a write function:)
Introduction:
Somatic is a generic 3D puzzle solver for arbitrary soma and pentomino
like puzzles. The soma puzzle is a set of 7 pieces, each build from 3 or 4
small cubes. With these pieces one can build a bigger cube made of 3x3x3=27 of
the smaller cubes and a lot of other figures. For an arbitrary set of pieces
and a figure with not more than 64 cubes Somatic can check whether this figure
can be build using these pieces and return one or more solutions. It does also
solve split figures which are not connected and partial figures, which do not
need all pieces to be build. Piece sets that can be solved include the soma
cube, the somaplus set, the doublesoma set, the bedlam cube and the pentomino
set.
Other sets may be specified through an input file. Figures and solutions can
be saved and read from a file again later. The GUI can be used to interactively
create figures, solve them and view the solutions. The piece set currently in
use can also be displayed.
GUI (Graphic User Interface):
A short description of the mouse functions in the GUI, since this is not
included in the help screen:
editing a figure (grey blocks):
By clicking with the left and right mouse button on the cubes you may add new
cubes or remove existing ones. Click and drag on the background with the left
mouse button will rotate the cube. Click and drag with the middle mouse button
or using the mouse wheel will zoom in or out.
solution (colored blocks):
Zooming and rotating is the same, additionally you can "explode" the solved
figure by clicking and dragging with the left mouse button.
pieces (extra popup window)
Here you can rotate each piece individually using the left mouse button.
Using the mousewheel or the middle button you can zoom and using the right
mouse button you can rotate all pieces together.
Console version:
to be filled
File format:
It is possible to save a piece set, a piece set and a figure or a piece set, a
figure and some solutions of this figure in a file. The format is based on
giving integer coordinates for each cube. The following example contains the
soma piece set, a figure made of 16 cubes and two solutions with different
pieces.
{ ( 7)
{ ( 3) ( 0, 0, 0) ( 0, 0, 1) ( 1, 0, 0) }
{ ( 4) ( 0, 0, 0) ( 0, 0, 1) ( 0, 0, 1) ( 1, 0, 1) }
{ ( 4) ( 0, 0, 0) ( 0, 0, 1) ( 0, 0, 1) ( 1, 0, 0) }
{ ( 4) ( 0, 0, 0) ( 0, 0, 1) ( 0, 1, 0) ( 0, 1, 1) }
{ ( 4) ( 0, 0, 0) ( 0, 0, 1) ( 1, 0, 0) ( 1, 1, 0) }
{ ( 4) ( 0, 0, 0) ( 0, 1, 0) ( 1, 0, 0) ( 1, 0, 1) }
{ ( 4) ( 0, 0, 0) ( 0, 0, 1) ( 0, 1, 0) ( 1, 0, 0) }
[ ( 16)
( 0, 0, 0) ( 0, 0, 1) ( 0, 0, 2) ( 1, 0, 0)
( 1, 0, 1) ( 1, 0, 2) ( 0, 1, 0) ( 0, 1, 1)
( 0, 1, 2) ( 1, 1, 0) ( 1, 1, 1) ( 1, 1, 2)
( 0, 1, 1) ( 1, 1, 1) ( 1, 0, 1) ( 0, 0, 1) ]
< ( 2)
{ ( 7) ( 24) ( 0, 0, 0) ( 10) ( 1, 1, 0) ( 24) ( 0, 0, 0)
( 0) ( 0, 0, 1) ( 8) ( 1, 0, 2) ( 5) ( 0, 0, 1)
( 24) ( 0, 0, 0) }
{ ( 7) ( 24) ( 0, 0, 0) ( 24) ( 0, 0, 0) ( 10) ( 1, 1, 1)
( 8) ( 0, 0, 0) ( 12) ( 0, 1, 2) ( 24) ( 0, 0, 0)
( 2) ( 0, 1, 1) }
>
}
The whole entry starts with '{' and ends with '}'.
In an entry, first the number of pieces is given, followed by the pieces. Those
start with a { bracket, followed by the number of cubes in this piece and
then the coordinates for each cube. They end with a } bracket. Each piece
needs to contain a cube at the position ( 0, 0, 0), the center cube and all
cubes need to be connected through sides.
Next a figure may follow. It starts with [ and ends with ]. First there
comes the number of cubes in this figure, followed by the coordinates for each
cube. The figure can not contain more cubes then all the pieces given have
together.
If a figure is given it may be followed by solutions. Solutions start with <
and end with >. First comes the number of solutions followed by solution entrys.
A solution starts with { and ends with }. First comes the number of pieces,
which has to match the number of pieces given above. Then follow pairs of
an orientation and a position for each piece. Legal orientations are 0..23, a
24 means that this piece is not in the solution. Other numbers are not allowed.
Of course the solution has to solve the figure with the pieces given above.
The orientation describes how the piece needs to be rotated around the center
block to solve the figure. To find out which cubes are covered by a piece you
first have to apply this rotation and then add the position vector to the cube
coordinates.
 orient.  matrix  orient.  matrix  orient.  matrix 
+++++++
  1 0 0   0 0 1   1 0 0 
 ( 0)  0 1 0  ( 1)  0 1 0  ( 2)  0 1 0 
  0 0 1   1 0 0   0 0 1 
+++++++
  0 0 1   1 0 0   0 0 1 
 ( 3)  0 1 0  ( 4)  0 1 0  ( 5)  0 1 0 
  1 0 0   0 0 1   1 0 0 
+++++++
  1 0 0   0 0 1   0 1 0 
 ( 6)  0 1 0  ( 7)  0 1 0  ( 8)  1 0 0 
  0 0 1   1 0 0   0 0 1 
+++++++
  0 1 0   0 1 0   0 1 0 
 ( 9)  0 0 1  ( 10)  1 0 0  ( 11)  0 0 1 
  1 0 0   0 0 1   1 0 0 
+++++++
  0 1 0   0 1 0   0 1 0 
 ( 12)  1 0 0  ( 13)  0 0 1  ( 14)  1 0 0 
  0 0 1   1 0 0   0 0 1 
+++++++
  0 1 0   1 0 0   0 0 1 
 ( 15)  0 0 1  ( 16)  0 0 1  ( 17)  1 0 0 
  1 0 0   0 1 0   0 1 0 
+++++++
  1 0 0   0 0 1   1 0 0 
 ( 18)  0 0 1  ( 19)  1 0 0  ( 20)  0 0 1 
  0 1 0   0 1 0   0 1 0 
+++++++
  0 0 1   1 0 0   0 0 1 
 ( 21)  1 0 0  ( 22)  0 0 1  ( 23)  1 0 0 
  0 1 0   0 1 0   0 1 0 
+++++++
In the example above in solution number one piece number two
{ ( 4) ( 0, 0, 0) ( 0, 0, 1) ( 0, 0, 1) ( 1, 0, 1) } has
orientation ( 10) and position b = ( 1, 1, 0). The rotation matrix to apply
is therefore A = ( ( 0, 1, 0),( 1, 0, 0),( 0, 0,1) ). For each cube c in the
piece Ac+b will give us the cube in the figure coverd by this cube. So, the
cubes in the figure covered by piece two are ( 1, 1, 0), ( 1, 1, 1),
( 1, 1, 1) and ( 1, 0, 1).
Links:
Updates and new versions can be found at the somatic homepage:
http://www.moerig.com/somatic/
Version 1.0 was originally created by
Heiko brotMachine Seim
brotmachine@gmx.de
http://www.cs.unimagdeburg.de/~seim/
Stefan happe Habelski
habelski@mail.cs.unimagdeburg.de
http://www.cs.unimagdeburg.de/~habelski/
Marc epikur Moerig
marc@moerig.com
http://www.moerig.com/
as a software lab for our lectures in computational visualistics at the
university of Magdeburg, Germany.
http://www.computervisualistik.de/
http://www.unimagdeburg.de/
There are now 6 Soma solvers that we currently know about:
1.
Bundgaard & McFarren's QBASIC program: Courtney made the
algorithms, Thorleif the graphics and user interface.
This is possibly the slowest solver on the list
(1.5 seconds per figure on the average), but it's QBASIC?
and the figures are easy to show in the web.
2.
Ross Canning's Windows solver: Slow (1
sec./fig.), but very easy to use, and small in size
to boot. Have the most amazing and easy graphical
user interface.
3.
Bob Nungester's Windows solver: Faster (.5
sec/fig.). NOTE: all of the above are timed for a
SINGLE solution.
4.
Sivy Farhi's DOS solver: Very fast. It
can solve multiple solutions in a second. No user interface.
5.
Bruce Cropley's BCSolve: Extremely fast, written in GNU C++
using binary bit flipping to achieve a blazing speed.
Solving multiple solutions in less than 1 second.
6.
Marc Moerig's Somatic: A fast solver, capable of handling
a large range of different puzzle types, including SOMA.

Submitted by Marc Moerig <marc@moerig.com >
Edited by Thorleif Bundgaard <thorleif@fambundgaard.dk>
BACK to news index