SOMA Crystal
SOMA News 20 Mar 2004
E-Mail.


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 "somatic-win-binary-20040318.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 NOT-only SOMA, but also a large range of other puzzles, so our SOMA-dataformat 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 NP-complete ( 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.uni-magdeburg.de/~seim/

Stefan -happe- Habelski
habelski@mail.cs.uni-magdeburg.de
http://www.cs.uni-magdeburg.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.uni-magdeburg.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@fam-bundgaard.dk>

BACK to news index