ILP Part 41 — Rubik’s cube

This is the forty first part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

We continue our exploration of riddles solvable by ILP. Today we are going to find solution for Rubik’s cube. Let’s begin.


There are lots of different Rubik’s cube, one of which is 2x2x2 cube similar to (Work by Mike Gonzalez, found on Wikipedia).
2x2x2 cube
There are various algorithms for solving these cubes, but we are not going to implement them directly. Instead, we need to know so called “God’s number” which is basically a maximum number of rotations required to solve cube starting from any state. These numbers are known for many cubes, e.g., for 2x2x2 it is 14 (as specified in 2x2x2 Cube – Speedsolving). So we know that we can take any cube and make at most 14 rotations to solve it.

Knowing this we can simply try every possible sequence of moves. Since we use ILP, we only need to define a “move” and what is “final position”.

Cube’s representation

We start with few helper classes representing cubes. Since solving algorithm is the same for cube of any shape (no matter whether it is 2x2x2 or megaminx), we would like to have these things independent.

First, we define colors of elements in order to be able to read code easily. Next, we define what any cube provider should define. These are: solver variables for all walls, method rotating single wall, number of walls, number of moves required to solve the cube (“God’s number”) and size of the wall. Next, we define provider:

First, _walls defines some initial state. Provider is responsible for specifying order of walls’ elements and moves, so we can choose any particular which suits our intuition/needs. Next, we define all moves. This “black magic” numbers represent which variables are replaced when we perform particular move. We need to specify all moves available for this cube.

Next, we implement interface. We simply return variables for all walls, for every transformation we extract source element and destination element, and we exchange them conditionally. Rest of the code should be obvious.

Now goes the algorithm.


This part is pretty easy. Since we know how many moves we need to perform, we iterate through all of them. For every move we create integer variable representing the move: it is a number of wall to rotate. Since we cane rotate it clockwise or counter-clockwise, we need to multiply possibilities by two. Also, since we might solve cube without performing all 14 moves, we add dummy move with no meaning.

Next, for every move we simply rotate wall and provider takes care of the whole transformation.

Finally, we constrain all walls to be of a single color.

And we are done.


With this approach we can easily solve any cube by implementing new providers. E.g., 3x3x3 is almost the same as existing code, megaminx requires a little more modifications.