## Snake cube

Few weeks ago one of my colleagues showed me this puzzle:

It's basically composed of 27 cubes, which are linked together by their faces. Each pair can be rotated around their common face. The aim is to fold the snake into a cube like this:

Needless to say, my first thought was to write a backtracker that solves the cube for me. After all it's more fun to write the program, than to play around with it for hours. It didn't take long. After I was done with that, I started to ask myself questions like:

- Are there other combinations with a single solution?
- Are there combinations with more than one solution?
- Are there palindromic snakes, that are solvable?
- How many different solvable snakes are there?

I quickly found the answers to those on Jaap's Puzzle Page. I won't repeat the results that are available there, go and check it out if you are interested. On the other hand, it did not contain the source code for the backtracker, so I decided to show you how something like that could be done.

My choice of language is C++, since that is the one I use most of the time now. (Also backtracking tends to be slow, so it's usually good idea to choose a fast language.) My initial solution was a quick an dirty one, which I re-factored until I was more or less happy with the result. It could still use some clean up (mainly a separation of the solver class from the solution data structure), but that is left for you as an exercise.

Here is the header file for the backtracker class without the includes:

typedef boost::multi_array SnakeCubeSolution_t; typedef std::vector SnakeCubePosition_t; typedef std::vector SnakeCubeConstraint_t; typedef std::tr1::function SnakeCubeSolutionCallback_t; class SnakeCubeTracker { private: SnakeCubeTracker(const SnakeCubeConstraint_t& constraint, SnakeCubeSolutionCallback_t callback); SnakeCubeTracker(SnakeCubeSolutionCallback_t callback); void tryAllStartingPositions(); void startSearchFromLocation(int x, int y, int z); void examinePartialSolution( unsigned int n, const SnakeCubePosition_t& position, int direction, int usedDims); void moveOneStepForwardWithSolution( unsigned int n, SnakeCubePosition_t position, int direction, int usedDims); void turn(unsigned int n, const SnakeCubePosition_t& position, int direction, int usedDims); bool isSolutionComplete(int solutionLength) const; bool isLegalMove(const SnakeCubePosition_t& position) const; bool isPositionOccupied(const SnakeCubePosition_t& position) const; bool fallsWithinCube(const SnakeCubePosition_t& position) const; bool isSnakePalindromic() const; bool isForOutput(const SnakeCubePosition_t position) const; bool isLexicographicallyLargerThenReversed() const; std::vector generateReverseDirections() const; std::map findReverseDirectionMappingForStandardOrientation() const; SnakeCubeConstraint_t constraint_; SnakeCubeConstraint_t snakeAlignment_; SnakeCubeSolution_t partialSolution_; SnakeCubeSolutionCallback_t callback_; SnakeCubePosition_t firstPosition_; std::vector directions_; friend void solveSnakeCube(const SnakeCubePosition_t& constraint, SnakeCubeSolutionCallback_t callback); friend void solveSnakeCube(SnakeCubeSolutionCallback_t callback); }; void solveSnakeCube(const SnakeCubePosition_t& constraint, SnakeCubeSolutionCallback_t callback); void solveSnakeCube(SnakeCubeSolutionCallback_t callback); void displaySolution(std::ostream& out, SnakeCubeSolution_t solution); |

The first thing that might be surprising is that all of the functions and members of SnakeCubeTracker are private. I did that because I wanted to make sure that this class is only used in conjunction with the solveSnakeCube functions. That gives the algorithm a clear and simple interface, and keeps the trolls away from implementation details. (I always feel funny about unnamed namespaces, since than I would have to declare the class in the source file.)

The first version of solveSnakeCube function expects a constraint integer vector describing the snake. In the vector 0 means a straight, and 1 means a corner cube. Corner cubes are the ones whose neighbors are on adjacent faces, while straight cubes have their neighbors on opposing sides.

The second argument (and the only argument for the overloaded version) is a callback function, that will be called for every solution. This is a design trick I use a lot, when implementing backtrackers. Most backtrackers that generate items are best implemented with recursive function calls, but that makes it very hard to implement them as iterators directly. A much easier way is to have them pass the results to a callback function or functor, that will take necessary action once it is called. The callback in this case receives a cube representing the solution, and a vector representing the constraint vector. The later is useful when the constraint was left empty, and we are generating statistics about all of the possible snake cube puzzles.

I don't think it would be worth to go through every single function, so I'll just let you skim through the implementation (click to open), and only discuss some of the less obvious parts.

The first function that I think may not be perfectly clear without some explanation is this one:

void SnakeCubeTracker::turn(unsigned int n, const SnakeCubePosition_t& position, int direction, int usedDims) { for(int i = 1; i <= std::min(usedDims,3); ++i) { if( i != abs(direction) ) { moveOneStepForwardWithSolution(n, position, i, usedDims); moveOneStepForwardWithSolution(n, position, -i, usedDims); } } if(usedDims < 3) { moveOneStepForwardWithSolution(n, position, usedDims + 1, usedDims + 1); } } |

Why is the for cycle cut of with a usedDims variable, and what does the second if do for us? The idea is, that the cube has lot's of symmetries, and so every solution would show upseveral times. To avoid that, I added a special constraint to all solutions: the n^{th}

dimension is not allowed to be used before the (n-1)^{st}, and in each dimension the first move has to be done in positive direction. That also makes something in SnakeCubeTracker::tryAllStartingPositions clear. If you look more carefully we are only using the smaller [0,1]x[0,1]x[0,1] cube as starting positions. All other positions are doomed to fail due to the symmetry rule used in the turn function.

The second interesting function: isForOutput. Why is it even necessary? It's only called when the solution is complete, and we already got rid of symmetry. The catch here, is that the cube is not the only thing that can have symmetries, but the snake as well. The problem is that if a snake is palindromic (or in other words symmetric) than we may find every solution twice. This function simply suppresses the callback for exactly half of the solutions if the snake is palindromic. To do that we have to find out which is the pair of the current solution. Since we had strict rules on how a solution should be oriented, we have to generate this orientation for the reverse of the solution, and then compare it with the current solution.

There is only one trick left, and that is also related to non palindromic snakes. When generating the stats for all snakes non palindromic snakes will be generated twice. So the functor class that accumulates the callbacks will need to filter exactly half of the non palindromic snakes. This can be easily done, by choosing the lexicographically smaller from the configuration, and it's reverse.