I got interested in this problem several years ago, as one of several unchosen options for a project in a graduate course that my wife was taking (or maybe it was someone else from work, I don’t remember). The problem was to implement an efficient algorithm for solving the 2x2x2 Rubik’s cube. I like this problem because it has several nice self-contained nuggets of mathematics in it. The motivation for this post is one of those little sub-problem nuggets (dense collision-free hashing of permutations) that makes for a particularly simple and elegant algorithm, solving not just a given scrambled cube but all possible configurations, in just 100 lines of Python code.
The 2x2x2 cube is much simpler than the more common 3x3x3 cube. The state space is obviously smaller; there are only or 3,674,160 possible configurations, compared with over for the larger cube. Also, there is a simple and compact representation for those configurations and moves between them. To see this, imagine fixing one corner cubie by holding it with the fingers of one hand, and applying moves by rotating any of the three faces not involving the fixed cubie (see image below; the fixed cubie is the one not visible). With these 6 basic moves– clockwise and counterclockwise quarter turns of 3 faces– it is possible to realize all possible cube states, consisting of permutations and orientations of the 7 non-fixed cubies.
From this perspective, we represent a cube state as a pair , where is a permutation in and is a 7-vector with elements in the finite field . The permutation indicates the positions of the cubies, and the elements of the vector indicate the 3 possible orientations of each of the cubies. (Although we can realize every permutation, not all possible combinations of orientations are possible; the orientations of any 6 cubies determine the remaining orientation. We can impose this constraint by requiring the sum modulo 3 of elements of to be zero.)
Each of the six basic moves may also be represented in the same way, with the calculation of a new cube state resulting from applying move to cube state given by
where the group action is the natural one permuting the coordinates of .
Ok, so where are we? The basic idea is to compute the graph of all possible cube states, where the 6 directed edges leaving each vertex correspond to the 6 possible quarter turn moves. If we then compute– and store– the shortest path spanning tree rooted at the vertex corresponding to the initial solved state, we effectively have a single “map” of the solution for every possible scrambled configuration of the cube.
Now for the interesting part, and the reason for this post: a paper by Myrvold and Ruskey (see the reference below) describes a very handy, linear-time algorithm for converting permutations in to and from distinct integers in . This is handy in this case because it allows us to use simple integer array indices in the adjacency list representation of the cube graph, as well as in the predecessor vector representation of the shortest path spanning tree. For reference, here is my Python implementation of their algorithm, excerpted from the Rubik’s cube code:
def rankperm(p): """Return rank in [0, n!) of given permutation of range(n). W. Myrvold and F. Ruskey, Ranking and Unranking Permutations in Linear Time. Information Processing Letters, 79 (2001):281-284. """ p = np.array(p) q = np.array(p).argsort() r = 0 for k in range(len(p) - 1, 0, -1): s = p[k] p[k], p[q[k]] = p[q[k]], p[k] q[k], q[s] = q[s], q[k] r += s * np.math.factorial(k) return r def unrankperm(r, n): """Return permutation of range(n) with given rank. W. Myrvold and F. Ruskey, Ranking and Unranking Permutations in Linear Time. Information Processing Letters, 79 (2001):281-284. """ p = list(range(n)) for k in range(n - 1, 0, -1): s, r = divmod(r, np.math.factorial(k)) p[k], p[s] = p[s], p[k] return p
You can download the full implementation at the usual location here, as well as on GitHub. In addition to the “business logic” that computes and saves the cube graph, there is also a GUI that lets you play with the cube or automatically solve it. Both pieces of code use Visual Python, the former using Numpy which is bundled with VPython, and the latter using the 3D graphics. The image above is a screenshot; as you can see, this is the result of just a few modifications and additions to the 3x3x3 version from earlier this year.
1. W. Myrvold and F. Ruskey, Ranking and Unranking Permutations in Linear Time. Information Processing Letters, 79 (2001):281-284. [PDF]