Tuesday, August 23, 2016

Things Get Done By Doing Them

I have been putting off working on finding the 240 unique solutions to the Soma Cube puzzle for several weeks because of my obsession with buying and reading more books on Group and Graph Theory in the hopes I will discover some methods that will make the search for unique solutions more fruitful and predictable.  I have succumbed to "Analysis Paralysis" and I intend to use the method my many artist friends use to alleviate this problem.  Put down the books, pick up the brush and paint.

Albeit it is not easy to see from the above picture I believe I have isolated the 240 unique solutions to a tree graph with 19 branches based on:

1. Locking the yellow "T" piece to a single edge
2. Permuting the violet "Crystal" piece about the locked "T"
3. Limiting the permutations of the violet "Crystal" piece to one side to account for reflected solutions due to the two "Chiral" pieces (colors auburn and blue).

Seems reasonable. . . Now I have 19 five piece puzzles.  I am adding a step "4" to further constrain solution searches.

4. Add the permutations of green "L" piece to each of the branches because (I think) since it can cover a complete edge it is doing more to constran the search space.  (This would good to prove . . . better however to just get on with variations on 19 five pieces puzzles).

So tonight I begin with branch 1. I will see how many I find and record them using the a cube grid map.  Conway and Guy presumably found 240 unique solutions in "one rainy afternoon."   I would love to know more about their method.  It is explained to a fair degree here:

Winning Ways for your mathematical plays:
http://www.fam-bundgaard.dk/SOMA/NEWS/N990201.HTM

I do not understand how they recorded and compared solutions to ensure they exhausted possibilities though.  I get the impression from another article that they worked from the constraints of which pieces can occupy the "Center Cube" and whether or not that piece provided a vertex or not.  Then from there exhausted two and three piece "swaps." This allowed them to arrive at the SOMAP (which I don't believe they drew that same afternoon)

The complete "SOMAP" is found:
http://www.fam-bundgaard.dk/SOMA/NEWS/N030518.HTM

My friend Merv Eberhardt has done some painstaking work interpreting the SOMAP along with normalizing solutions from the "rainy saturday":

A way to solve the SOMAP:
http://www.fam-bundgaard.dk/SOMA/NEWS/N160509.HTM

The Normalization of SOMA solutions:
http://www.fam-bundgaard.dk/SOMA/NEWS/N151008.HTM

Merv finds the two solution sets don't match.  There appear to be "reflections" due to the two chiral pieces. Which is a motivation for me to use the 19 branch tree method that I believe limits the serach space to a single set of 240 solutions. . . I got the idea to do this from Peter Christoph Orth's work:

All solutions of the Soma cube puzzle:

http://www.sciencedirect.com/science/article/pii/0012365X85901608

Wish me luck.  I have been pondering this since I first got the puzzle as a Christmas present in 1968.  

I know that with the current constraints I have developed to limit the search space I could now write or borrow an exact cover program (like this one):

Algorithm X in 30 lines!
http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html

and find the solutions that way but I am interested in seeing if I can find out more about what the variety of wrong looks like and perhaps graph aspects of the non solution space to see if there is something enlightening or beautiful in it.


Your comments, criticisms and kind suggestions are of course most welcome. 

No comments:

Post a Comment