RubikTwoPhase, a Python two-phase solver that finds near-optimal cube solutions

What the project is and what it costs to run

This project implements the fully developed version of the two-phase algorithm for solving the Rubik's Cube in Python. The README is honest about the trade: Python is much slower than languages such as C++ or Java, but the implementation is efficient enough to solve random cubes in fewer than 20 moves on average within a few seconds, even on relatively slow hardware such as the Raspberry Pi 3.

The cost is in the setup rather than the runtime. The package is on PyPI and installs with a single command:

pip install RubikTwoPhase

But some tables need to be generated, and the README says this happens only during the first run. Those tables occupy approximately 80 MB of disk space and may take half an hour or more to generate, depending on your hardware. The README then makes the connection explicit: it is precisely these computationally expensive tables that enable the algorithm to operate efficiently, usually finding near-optimal solutions.

That is the shape of the algorithm. The two-phase approach splits the problem into finding a set of cubes that all satisfy the same coarse constraints and then searching within that set, and the precomputation is what makes the second phase fast. You pay once, and then every subsequent solve is quick.

The README is careful about who this is for. If the goal is simply to solve the cube and explore its patterns, Cube Explorer might be the better choice. This repository is for the case where you want a deeper understanding of the intricacies of the two-phase algorithm, or where you are building a cube-solving robot that has to produce near-optimal solutions.

That last use case is the one that justifies the whole design. A robot that has to minimise the number of moves because each move takes time is exactly the situation where a solver that returns a solution in 19 moves rather than 30 is worth an hour of table generation.

The API, the cube string and the move notation

The package is imported as a module and the interface is small. You import the solver module:

>>> import twophase.solver as sv

A cube is represented by its cube definition string, and the solved cube is a specific 54 character string:

UUUUUUUUURRRRRRRRRFFFFFFFFFDDDDDDDDDLLLLLLLLLBBBBBBBBB

with a scrambled cube given the same way:

>>> cubestring = 'DUUBULDBFRBFRRULLLBRDFFFBLURDBFDFDRFRULBLUFDURRBLBDUDL'

The README points at enums.py for the exact format of the string.

Solving is a single call:

>>> sv.solve(cubestring, 19, 2)

The three arguments are the cube, a desired maximum solution length of 19 moves, and a timeout of 2 seconds. The README explains the behaviour when the timeout is reached: the shortest solution found so far is returned, even if it exceeds the desired maximum length. That is a sensible design, because the maximum length is a target and the timeout is a hard bound, and a solver that returns nothing when the clock runs out is less useful than one that returns a slightly longer answer.

The output is a move sequence:

L3 U1 B1 R2 F3 L1 F3 U2 L1 U3 B3 U2 B1 L2 F1 U2 R2 L2 B2 (19f)

where U, R, F, D, L and B are the Up, Right, Front, Down, Left and Back faces, and the suffixes 1, 2 and 3 are clockwise rotations of 90, 180 and 270 degrees respectively. The trailing 19f is the solution length with a flag.

If you would rather allocate a fixed amount of computation to each search and take the shortest solution found within it, you pass a maximum length of zero instead:

>>> sv.solve(cubestring, 0, t)

The performance module lets you measure the algorithm on your own machine, generating random cubes and reporting the distribution of solution lengths:

>>> import twophase.performance as pf
>>> pf.test(100, 0.3)

There is also a solveto variant for solving to an arbitrary target pattern rather than to the solved state, where the target is given as a goalstring:

>>> sv.solveto(cubestring, goalstring, 20, 0.1)

That one is worth noting for robot work, because the ability to solve to a pattern rather than to solved is what you need if the cube is being inspected rather than solved.

What the solver arguments control

The two arguments to solve are where the design shows.

The first is a maximum solution length, and the second is a timeout in seconds. They are not the same thing and the distinction matters. The maximum length is a target that the search tries to satisfy, and the timeout is a hard bound on how long the search runs. When the clock runs out, the README says the shortest solution found so far is returned even if it exceeds the desired maximum.

That behaviour is a deliberate choice and it is the right one for a robot. A solver that returned nothing when the timeout hit would force the caller to handle an empty result, and the only sensible thing to do with an empty result is to use the best answer found so far anyway. The two numbers let you express the two requirements separately: I want solutions of at most nineteen moves, and I am willing to spend two seconds looking.

The alternative form, passing a maximum length of zero, changes the priority. With a maximum of zero and a fixed time budget t, the search spends its whole budget and reports the shortest solution it found, whatever the length. That is the mode for batch work, where the total time is what matters rather than the length of any one answer.

The solveto variant adds a third dimension. Instead of solving to the solved state, it solves from one pattern to another, with the same maximum length and timeout arguments. For a robot that is inspecting a cube rather than scrambling it, that is the operation you actually need.

The server mode and how it fits against the alternatives

The server mode turns the solver into a small HTTP service, which is what you want when the caller is a robot or a script rather than a Python program.

You can start it in the foreground:

>>> import twophase.server as srv
>>> srv.start(8080, 20, 2)

or run it in a background thread:

>>> import twophase.start_server as ss
>>> from threading import Thread
>>> bg = Thread(target=ss.start, args=(8080, 20, 2))
>>> bg.start()

A successful startup prints messages like Server socket created and Server now listening. The arguments are the port, the desired maximum solution length and the timeout, so a server on 8080 with a maximum of 20 moves and a 2 second timeout behaves like the call above with different defaults.

The client side is the simplest thing imaginable, which is the point. A browser on the same machine puts the cube string in the path:

http://localhost:8080/DUUBULDBFRBFRRULLLBRDFFFBLURDBFDFDRFRULBLUFDURRBLBDUDL

A browser on a remote machine does the same against the host and port where the server runs, and the README also shows using netcat for a command line client.

Putting the cube in the URL rather than in a request body is a deliberate simplification, and it has consequences. It makes the server trivially usable from anything that can make a GET request, which is why a browser works with no page of any kind. It also means there is no authentication, no input validation and no rate limiting, which is fine for a service on a local network and wrong for one exposed to the internet.

The alternatives come down to two. Cube Explorer is what the README points you to if your goal is simply to solve the cube and explore its patterns. A robot that needs near-optimal solutions in its own language would reimplement the algorithm in C++ or Java, which is the case the README describes this project as being for.

What this project gives you is the algorithm in a language you can read and modify, with the reference implementation of the two-phase approach rather than a wrapper around someone else's solver. For understanding why the move count comes out where it does, and for adapting the search to a different machine, that is the value.

The one thing to check before committing is the table generation time on your target hardware, since the Raspberry Pi 3 figure in the README is the one that matters for a robot, and half an hour of generation is a real cost for a device you might power cycle.

Editorial conclusion

Adopt RubikTwoPhase if you need a reference implementation of the two-phase algorithm, near-optimal solutions, or a cube-solving robot that has to produce short move sequences. Skip it if you just want to solve cubes, because Cube Explorer does that faster and with none of the setup. Verify first by generating the tables on the machine you intend to use and timing the generation, since half an hour on a Raspberry Pi 3 is a realistic figure rather than a worst case.

Frequently asked questions

Official sources

1. hkociemba/RubiksCube-TwophaseSolver on GitHub
2. Issues
3. License: GPL-3.0
4. README