# Implementing a brainball solver

Some years ago, I got a "brainball" as a present, a game similar to a rubiks cube and supposed to be pretty hard. I was not able to solve it by hand, so I decided to write a solver in Rust.

## The puzzle

The brainball is essentially a ring subdivided into 13 segments, numbered 1 to 13. Each segment has a front and a back side, both labelled with the same number, but one side being white, the other being yellow.

The ring can be shifted around, and the ball can be flipped in a way such that certain numbers stay in place, while others do not.

A more detailed description can be found on https://www.jaapsch.net/puzzles/brain.htm. This site also contains a solver, but it is not very fast and its solutions are far from optimal.

## Representation

It is clear that we can - without loss of generality - assume that the white 13 is at a certain position, so that we only need to store the remaining positions.

That is, we must store 12 numbers with their associated color. Representing 12 numbers requires 4 bits, the additional 1 requires 1 additional bit. Thus, we can squeeze 12 color-number pairs into 60 bits, meaning that we can use a single 64-bit integer to store the whole brainball. I wrapped this integer in an own struct `SBall`

. The function `new_from_vec`

constructs a new `SBall`

from a more user-friendly representation.

## Rotations and flips

Now, to examine what happens upon an interaction, we need a way to modify a configuration. Since rotation does not actually pose a significant challenge in real life, we only implement flipping the brainball at a certain index. Flipping is then done by rotating to this particular index, do the flip, and rotate the ball back so that the white 13 is at our predetermined spot (i.e. we canonicalize the representation).

Since flipping is a pretty expensive operation (when done inside a hot loop), we do all the flips using precomputed lookup tables that are computed in a build script and included into the program.

## Solving the brainball

Solving the brainball is done in two steps: Since we have 13 slots, where 13 of them are "the same due to rotation", we have \(12!\) possibilities for the remaining 12 numbers stored in `SBall`

, and each of these numbers carries a color, leading to \(2^{12}\) possibilities for the colors, totalling \(12! \cdot 2^{12}=1961990553600\) possibilities.

From this we can assume that 14 moves could be enough to reach all possible combinations, so that we could - in theory - backtrack until depth 14, trying to reach the solution.

In practice, however, branching until level 14 fans out into far too many possibilities. Thus, as a trick:

- Starting from a solved configuration, we backtrack until depth 7, remembering all the configurations reached until this level. Instead of remembering the whole sequence of moves to reach certain configurations, we only store how many steps it took, as this was faster in my tests.
- Starting from our configuration to be solved, we backtrack until depth 7 and see if we encounter a configuration that we already saw in the previous step. If this is the case, we check if we found a shorter solution and remember the data for this solution.
- Then, we reconstruct the moves executed in the first step and concatenate these to the ones found in the second step.

## Backtracking

The backtracking algorithm is implemented in a way that allows the rust compiler to inline quite a bit. We pass a significant amount of arguments as generic parameters (instead of regular, run-time arguments) so that the optimizer can see through the constants and optimize them away: `NumDepth`

denotes the current backtracking depth; `NumLastPriFlip`

and `NumLastSecFlip`

offer a very cheap optization avoiding flipping the brainball back-and-forth, essentially doing a no-op; last, `FnSuccess`

allows the backtracking algorithm to be customized and to be aborted early.

## Outcome

The previously outlined strategy found solutions to all my randomly generated testcases (more than 10000). The whole backtracking routine takes less than 15 seconds on my 2014 laptop.

In the (hopefully very unlikely) case that the strategy cannot find a solution, there is a fallback mechanism that composes a solution from predefined moves, and try to minimize this solution by exploiting that certain configuration changes can be reached in fewer moves.