Tuesday, September 27, 2016

Graphs and Solutions Representation

I have found a little more than fifty solutions from three of the nineteen beginning positions of the yellow "Tee" and violet "Crystal" pieces I am proposing will root two hundred forty unique solutions.   Originally I had  conceived of recording all of the solutions on paper and colored pencil then cutting up the solutions and arranging them on a wall to create a tree graph representation that would grow as I found more solutions.  Alas I do not have a big enough wall.

The figure below shows a previous tree graph made using yEd graph editor:
https://www.yworks.com/products/yed

This tree graph if printed out with a 12 point font is about 8 feet x 8 feet.  It certainly has the potential to be a very beautiful representation but I haven't figured out how to get the node colors yet.

The solutions used in this instance were from and existing set from a paper by Peter Orth that provided a table of all the solutions normalized to the Tee on the front edge:
http://www.sciencedirect.com/science/article/pii/0012365X85901608


I have settled on recording the solutions directly into a spreadsheet page that translates the entered solutions on a cube grid into formats compatible to yEd.

This is what I have so far.  It looks interesting and might be understood by someone particularly if there were lots of Soma puzzles laying around near the graphs.  It would fit on an 11x17 sheet size.  The next tree will be more challenging as it has thirty two solutions

Thursday, September 15, 2016

A Little Progress. Trees Grow From Seeds After All

Finally figured out how to load images as nodes in yEd graphing app. This is the beginning of the first of 19 tree graphs that will organize 240 Soma cube solutions to illustrate the structure of the solution sets. Each node label contains the 1 to 27 "cubelet" the piece occupies so it is also a robust graph showing the complete solution. Tree 1 has nine cubes. Tree 2 has thirty two. . .that is going to be an interesting graph.



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. 

Wednesday, May 18, 2016

Somap Tips, Tricks and Other Stuff



Below the ***** is the text of the email Merv sent me about a week ago with some notes by me.  The code used by Conway and Guy describe the solutions and their relationships is not a trivial deciphering task.   Tips and tricks to help you navigate the Somap.

Above is a work in progress that I think will give the map more color and verbosity. Also navigation tools utilizing graph theory and graph SW are put into play. More details to follow.


*****************************************************************************
How I Solved the SOMAP by Merv Eberhardt of Huntsville, Alabama.

This entire effort was based on reverse engineering of the seven SOMA pieces to achieve the designated SOMAP cube codes as discussed in the SOMA Newsletter, 18May2003.
http://www.fam-bundgaard.dk/SOMA/NEWS/N030518.HTM

The key concepts are, DEFICIENCY, CENTER, and DEXTERITY. The designation of the pieces is based on the piece colors:
1=B (Brown)
2=Y (Yellow)
3=G (Green)
4=O (Orange)
5=U (blUe)
6=R (Red)
7=A (blAck)

The orientations of pieces 1, 2, and 4 determine the dexterity values. 

1 = a small capital "L"
2 = a large capital "L"
4 = a "Z"


Dexterities 0-7:
Dexter = Looks like a letter L or Z.
Sinister = looks like a backward letter L or Z.
Orientation is based on the orientation on the edge.

Dexterity   Piece 
Number      Number
            1 2 4
0           0 0 0
1           1 0 0
2           0 2 0
3           1 2 0
4           0 0 4
5           1 0 4
6           0 2 4
7           1 2 4



My attention was drawn to the 14 gy-go-oy transitions in the middle of the SOMAP and I started at the bottom mid-right.  My initial goal was to identify the solutions to the RU2-RU0-RU4-RU2 transitions.  Those transitions are also applicable to the other gy-go-oy transitions at U2-U0-U4-U2; BU2-BU0-BU4-BU2; B2-B0-B4-B2; R2-R0-R4-R2; BR2-BR0-BR4-BR2; A2-A0-A4-A2; and A3-A1-A5-A3.

(Notes from EdV:
1. Lower case letters on edges are the colors of the pieces that get swapped. red, orange, yellow, green, blue, brown, black.
2. Lower case letters in a node indicate which solution iteration of the Deficient, Center and Dexter properties. 
3. Capital letters are Deficient piece and Center piece in that order if there is only one capital letter this indicates that the piece is both the Deficient piece and the Center piece.
For instance RU4e means:
aR (Red)is Deficient. It does not contribute any of its cubes to any of the eight vertices of the cube solution.
b. U (blUe) is Center. One of its cubes occupies the center cube of the cube solution.
c. 4 is the Dexter property. Piece 4 which is the "Z" shaped orange piece must when viewed as "sitting on the edge" it occupies with two cubes it will appear as a proper letter "Z". (I hope that is right because it really is not simple to interpret)
d. e is the "e"th or fifth cube solution for the RU4 series of Deficient, Center and Dexter properties.)
     
Back to Merv:

Starting with the <oy> transition between RU4a and RU2a, RU4a<oy>RU2a.
I recognized that the RU2a layout required a dexterity of 2 to be satisfied with the (Y)ellow piece
and that the RU4a layout would require a dexterity of 4 to be satisfied with the (O)range piece.
I determined that the following layouts on the bottom layer would provide the proper transition and dexterity values.

         Bottom  Layer               Bottom  Layer
    RU4a              RU2a
  Y Y Y    Y Y O
  O O<oy>O O
  O O x    O x

The next consideration was the <go> transition RU0a and RU4aRU0a<go>RU4a. The (G)reen piece would not affect the dexterity value while the (Y)ellow piece would change its dexterity value from 4 to 0. It was somewhat obvious that one of the ends of the Green piece would occupy the remaining space in the bottom layer and run vertically along the right-front edge; but what should be its orientation in the middle and top layers with respect to the <go> transition? And how would this be represented in the first two layouts, i.e. RU4a and RU2a?

This lead to the following:

T  x x x    x x x    x x x
O  x x x    x x x    x x x
P  x x O    x x G    x x G
    RU0a     RU4a     RU2a
I  x x O<go>x x G<oy>x x G
D  x x O    x x G    x x G
                         
B  Y Y Y    Y Y Y    Y Y O
O  Y G O    Y O O    Y O O
T  G G G    O O G    Y O G

The <gy> transition RU2b and RU0a was straightforward.
The Y and G pieces would exchange positions in an obvious way such that would change the dexterity value of the Yellow piece from 0 to 2.

T  x x x    x x x    x x x    x x x
O  x x x    x x x    x x x    x x x
P  x x O    x x O    x x G    x x G
    RU2b     RU0a     RU4a     RU2a
M  x x x    x x x    x x x    x x x
I  x x O<gy>x x O<go>x x G<oy>x x G
D  x x O    x x O    x x G    x x G

B  G G G    Y Y Y    Y Y Y    Y Y O
O  Y G O    Y G O    Y O O    Y O O
T  Y Y Y    G G G    O O G    Y O G

So far, three pieces, G-O-Y, have been arranged into the bottom, middle, and top layers.
The O piece has been placed so that its dexterity value of 4 was properly considered.
The Y piece has been placed so that its dexterity value of 2 was properly considered.

The four corners in the bottom layer and one corner in the top layer have been placed.

To complete the layouts, the orientation of the remaining four pieces, i.e. A, B, R, and U, must be determined.
The following criteria must be met: piece R must be deficient,
that is it must not occupy any of the remaining three cube corners.
Pieces B, U, and Y must occupy the remaining three cube corners. 
Piece 1=B must be in a sinister position so as not to add to the dexterity values.   
And finally, piece U must occupy the space in the center of the cube.

The resulting layouts are as follows:

T  A A B    A A B    A A B    A A B
O  A R R    A R R    A R R    A R R
P  U R O    U R O    U R G    U R G
    RU2b     RU0a     RU4a     RU2a
M  A B B    A B B    A B B    A B B
I  U U O<gy>U U O<go>U U G<oy>U U G
D  U R O    U R O    U R G    U R G

B  G G G    Y Y Y    Y Y Y    Y Y O
O  Y G O    Y G O    Y O O    Y O O
T  Y Y Y    G G G    O O G    Y O G

With the identification of these three swaps between the four layouts, all of the remaining SOMAP cube codes can be revealed from the specified two and three piece swaps and cube codes throughout the SOMAP.
I would like to point out several challenges appear elsewhere on the SOMAP. 
They consist of 23 three-way patterns that consist of swaps between <ab>, <br>, <bu>, and <roy>.
And a swap <guy> between four solutions.

These must take into account differences between the three variables of cube codes, i.e. deficiency, center, and dexterity. A true test of SOMAPmanship. Good luck. Let me know of your success.
*****************************************************************

Here is the Somap enhancement I am considering:



Compact sub-graphs for each cube solution consisting of:
1. Nodes that will contain 
   a. Color of the piece
   b. EVFC (Edge, Vertex, Face, Center) properties of the piece
   c. A node position that is indicative of where its first cube         resides in the 1-27 cubes of the solution
2. Edges are numbered to indicate the number of shared cube faces touching.

Sort of a "Friends Graph" of the pieces in a particular solution.  To make the drawing of the compact graph doable and fun (I hope) I am using Edgy (a graph manipulation SW implemented in SNAP):

http://snapapps.github.io/edgy/app/edgy.html

It starts with an input cube grid graph shown below (after coloring it in of course to match a solution found using a set of properly colored cubes)

the Edgy program sorts through the colors and tallies up the edges and node EVFC properties and draws the compact sub-graph which is then copy pasted into the SOMAP.

I will be maintaining a repository of my Edgy work here:
https://github.com/EdV2/Soma-Cube-Solution-Grapher


Sunday, May 15, 2016

An Artistic Approach to Mathematics

Fig. 1 Twenty-seven Soma Puzzle Cubes that form "The Crystal" used to form a much larger crystal.
I am a lover of patterns and color. I make "math manipulatives" from simple materials at hand, paper, tape, crayons, wood and of late 3D printing.  I volunteer at several after school programs in Minneapolis making and helping others make everything from counting blocks to working clocks.


My favorite manipulative is the Soma Cube by Piet Hein:
https://en.wikipedia.org/wiki/Soma_cube

There are 240 unique solutions to the cube puzzle which I have been pondering since I got the puzzle as a Christmas gift in 1969.  How would one even approach the cataloging solutions and making sure there were no repeats?  

If one is lost one certainly can use a map and it turns out Soma has one.  It is called the Somap and can be found here:
http://www.fam-bundgaard.dk/SOMA/NEWS/N030518.HTM



The instructions are not super easy to understand but another Soma enthusiast has sorted it out.  I am forever in your debt Merve Eberhardt. Merv has also done some other interesting work normalizing the existing solutions:
http://www.fam-bundgaard.dk/SOMA/NEWS/N151008.HTM

Fig. 2 The Somap

Above (Fig. 2) is the Somap, a summary of Soma cube solutions and the structure of the solution relationships, I also find it to be a beautiful work of art.  Large and small symmetries and departures from symmetry.  From a graph theory perspective the vertices are shorthand(based on key piece properties) solutions and the edges are labeled with the Soma piece swaps to get from one solution to the next.

It is explained here:
http://www.fam-bundgaard.dk/SOMA/NADDICT/Addict42x.gif

Let's look at some worked out examples.  It helps to make a Soma set that has the colors and codes on them (Fig. 3)
Fig. 3

I will detail the examples in my next post but for the time being I invite you to join in the effort to decode all of the Somap solutions so they can be compared to and cataloged with the existing table of solutions:
http://www.fam-bundgaard.dk/SOMA/NEWS/N151008.HTM

If you are interested in collaborating please contact me and I will build you a set of Soma blocks with the proper colors and codes on them.