Snake Cube

Last December, a young cousin of mine got a snake cube for Christmas. He showed it to me. Even though I have never seen that thing, I took a low pitched voice, hinted with a lot of self confidence that it was very easy to do/undo it. In the manipulation, I unfolded it and... was completely unable to fold it again into its original cube shape. I was a little bit ridiculous  and later decided that at least there is a good way to turn this domestic defeat into a learning experience: I should solve this snake cube.. No ! All snake cubes !! Forever !!!  

Nothing difficult, of course, but the problem still requires to be approached in an organized fashion.

Introduction

A snake cube puzzle is a string of 27 cubes connected by an elastic that goes through each cube. The elastic goes either straight through the cube, from one face to the opposite, or turns inside the cube and goes from one face to an adjacent. The aim of the game is to fold it into a 3x3x3 cube, if possible. It is usually quite difficult to do it the first time, when a snake does not have many solutions.

Our objective here is to find all possible solution snake cubes (ignoring rotations and reflections), and sort them to try and make sense of how this population is distributed. To be more specific, any 2 snakes that are identical after a series of rotations and/or reflections are considered one solution.

A solution snake cube is an undirected Hamiltonian path in the 3x3x3 grid graph.

In order to explore the possibilities in an orderly and economical way, we first describe a method to travel inside the grid graph, starting from specific first few vertices all the way to Hamiltonian path. We try to avoid doing redundant searches. Indeed the cube has many symmetric axes, and many symmetric starting points. There are many possibilities to explore so this concern for optimisation is no luxury.

Once the search is complete, we sort the solution snake cube (the "paths") by letter sequence. A letter sequence is a string of 27 letters that define a snake cube puzzle.

• E for and end cube.
• S for a 'straight' cube; the elastic goes from one face to the opposite face.
• C for a 'corner' cube; the elastic goes from one face to an adjacent face.

Within all the paths for one sequence, we determine the "base" paths, ie those which cannot be deducted one from the other by a combination of rotations and/or reflections ("transformations"). This step requires a lot of calculations so all transformation are computed beforehand. 

Finally we get all the base paths and can examine the results.

Poker 4: Monte Carlo Analysis

Why using Monte Carlo to compute poker probabilities ?
Because in a number of cases, the number of possibilities is way to large to be explored.

For example, computing the equity of on player's PreFlop hand that has NbOpp opponents sitting around the table requires to go through N different game configurations:
\[\left(
\begin{array}{c}
 52-2(\text{NbOpp}+1) \\
 5 \\
\end{array}
\right)\prod _{i=1}^{\text{NbOpp}} \left(
\begin{array}{c}
 52-2i \\
 2 \\
\end{array}
\right)\]
Even a very fast hand evaluator on a modern machine does not parse much more than 300 millions hands per second, which leaves the exact computation of a PreFlop hand equity for 4 or more players completely out of reach.

As cheesy as it may be, the table below helps visualizing the kind of numbers at play.

Naturally the numbers are meaningless past the 1 or 2 opponents case.
So computing the equity of PreFlop hand in the general case is practically impossible.
Let us turn to Monte Carlo simulations to at least approach these values.

Poker 3: Exhaustive Analysis

There are 169 different possible PreFlop hands:

• C(13,2) = 78 suited hands
• C(13,2) = 78 offsuited hands, excluding pairs
• 13 pairs

For a given such Pre Flop hand, let us generate all possible 5 table cards. There are C(50,5) = 2,118,760 different tables. Assuming each set of table cards is equally likely, i.e. neglecting the other players hole cards, we can compute the distribution of hand ranks associated to a PreFlop hand.