A game: How to model the Soma Cube

I have challenged myself to build a Neo4j solver for the Soma Cube, and share it with the community.



There are 7 distinct pieces. They can be assembled in multiple ways to form a cube. I would like to put Neo4j to the task of providing all possible solutions of the game (that form a cube).

These pieces have inner corners and outer corners, and most likely I need to check that every inner corner gets occupied by an outer corner of another piece. I want to be able to represent the 3D shape of each piece, well enough to determine how those pieces can be oriented to fit together to form a cube, without breaking the laws of physics. It would be cool if I could use the new 3D Spatial Data type somehow.

Just for clarity: I'm not asking for a complete solution; I do actually want to solve it myself. But I would welcome any suggestion about how to model the separate pieces in the game. I can think of an approach to solving this outside Neo4j, using a scripting language and a 3D Matrix, but that's not the challenge I want to solve.

I could imagine a graph modeling various aspects of this. A graph of the connections that assemble single cubes into 3D pieces, a graph of combinations of 3D pieces into complete cubes. A graph of choices to make when assembling, which is more of a decision tree with many branches. A Cypher query to traverse that decision tree and filter out invalid solutions (current glob exceeds 3 cubes in any dimension, terminal glob must have no gaps, or unfilled inner angles, as you describe it).

The new 3D spatial data type could be used to describe the relative positions of parts of pieces, but I think this might make things harder, because it disallows rotations of pieces, requiring changing the 3D point every time you rotate. Perhaps you would create all possible orientations as separate pieces, in which case that problem goes away, as long as you then have a rule to never use two of the same type in the solution.

One idea would be to not only solve the some cube, but derive it from scratch. Imagine generating all possible pieces made of one, two, three, four, five, etc. cubes, and assembling all into 3x3 cubes, and scoring the best using some score based on number of pieces or perhaps piece sizes. Minus points if pieces are not unique. Perhaps the soma cube of 7 unique pieces is the only solution for a 3x3 cube?

Thinking more about the graph side of this, I think the decision tree is the way to go. The first decision is which piece to start with, and that has seven branches. At the end of each is the decision of which second piece, which orientation of that piece and which direction to attach, which would lead to many, many branches. The decision tree will be very bushy indeed. If you generated the complete graph of all possible decisions, then you could use a query to traverse the graph and find all possible solutions.