Graph Theoretic Methods for SOMA.
SOMA is on one hand, an extremely simple puzzle using only 7 pieces.
On the other hand, it may involve complex mathematical theories.
From Ed Vogel
See also:
News 06.08.08 Minnesota State Fair
and
News 02.06.21 World's Largest cardbox SOMA.
This time Ed Vogel (Minneapolis - USA) is discussing some mathematical ideas.
So let us follow his argumentation.
Which can also be seen on the "Math is fun Forum" page:
http://www.mathisfunforum.com/viewtopic.php?id=21536
Here are a few other links from Ed
http://en.wikipedia.org/wiki/Soma_cube
http://www.mathematische-basteleien.de/somawuerfel.htm
Ed asks - Are There Graph Theoretic Methods for Polycube Puzzles?
I would like to discuss "Tree graphs and recording/displaying solutions to the SOMA cube puzzle".
It seems reasonable to me that the solutions can be shown on a tree graph but:
1. How best to do it? Start with tables and then sort the tables before graphing?
2. How much information is needed? I think the piece color occupying which of 8 vertices may suffice.
3. Are other graph methods of use to:
3..a. determine a bound on the number of solutions?
3..b. determine allowable piece positions?
1. A tree graph would describe the 240 solutions and reflect left and right due to the similar helix pieces.
There are also as many 16 solutions that begin with the same three pieces in the same position
which would become major branches off of the trunk.
http://www.fam-bundgaard.dk/SOMA/NEWS/N030518.HTM
2. A weighted graph of the pieces "touching" in all 240 solutions would be a way
to illustrate the constancy of some of the pieces.
http://www.fam-bundgaard.dk/SOMA/NEWS/N990201.HTM
SOMAP |
Turns out their is more branching than I thought.
This sub branch occurs in several other branches as well.
Anytime the preceding 5 pieces leave the green L and the orange Z as the last pieces there
is a symmetry operation that can be utilized to show another unique solution.
Eventually I should end up with a graph like this one:
A tree graph of 14 of the 240 solutions
Turns out their is more branching than I thought. This sub branch occurs in several other branches as well. Anytime the preceding 5 pieces leave the green L and the orange Z as the last pieces there is a symmetry operation that can be utilized to show another unique solution.
Eventually I should end up with a graph like this one:
There is a very interesting approach here to graph theoretic methods for tiling trominoes
which I think could shed some light but get lost in their notation around page three:
Graphs of Tilings (specifically a simple trominoes puzzle)
http://web.calstatela.edu/faculty/sheubac/papers/Graphs%20of%20Tilings.pdf
Second link to the text
Perhaps if someone were to get a good handle on the methods used in "Graphs of Tilings"
some interesting non computer methods could be developed to chart SOMA solutions as tree
graphs and also as directed graphs.
Thank you to Ed Vogel, for these complex thoughts,
and for sharing them with us.
Edited by Thorleif Bundgaard <thorleif@fam-bundgaard.dk>
BACK to news index