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:

from visual import * 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 = array(p) q = 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 * 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, factorial(k)) p[k], p[s] = p[s], p[k] return p

You can download the full implementation at the usual location here. 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.

Reference:

1. W. Myrvold and F. Ruskey, Ranking and Unranking Permutations in Linear Time. *Information Processing Letters*, **79** (2001):281-284. [PDF]

hello emcontrei an error

Computing cube graph…

Traceback (most recent call last):

File “C:\Users\Henrique\Downloads\rubik2\rubik2.py”, line 101

g = cubegraph()

File “C:\Users\Henrique\Downloads\rubik2\rubik2.py”, line 72, in cubegraph

cube = unpackcube(i)

File “C:\Users\Henrique\Downloads\rubik2\rubik2.py”, line 46, in unpackcube

q = array(map(ord, base_repr(q, 3, 6)[-6:])) – ord(‘0’)

TypeError: unsupported operand type(s) for -: ‘map’ and ‘int’

I’m not sure what is causing this error. Can you verify what version of Python and Visual Python you are using?

hello, thanks for replying.

I am using version VPython-Win-Py3.2-5.74 for windowns and 64-bit Python 3.2.2

The code was written using Python 2.7, so there may be some issue with either Python 3.x, or possibly with the 64-bitness of the underlying Numpy installation? The VPython download page seems to suggest that they only “directly” support 32-bit; did you get your 64-bit installers from a third party?

python is actually 32 bits, written in the wrong, so if I install python 2.7, which vpython have to install?

I just tested without problems on my laptop which is running 2.7.2 with VPython 5.71. But I would not expect any problems with the latest recommendation on the VPython download site, which has links to 2.7.5 and 6.05. (In other words, this looks less like a problem with any specific version, but with not installing whatever *pair* of versions that VPython expects to go together.)

I installed python 2.7 and 2.7 vpython, when running rubik2.py happens the following error

Computing cube graph …

Traceback (most recent call last):

File “D: \ rubik2 \ rubik2.py”, line 101

cubegraph = g ()

File “D: \ rubik2 \ rubik2.py”, line 73, in cubegraph

g.append ([packcube (movecube (cube, move)) is moving in cubemoves])

File “D: \ rubik2 \ rubik2.py”, line 40, in packcube

rankperm return (p) * 6 ** 3 + dot (q [: 6] 3 ** arange (5, -1, -1))

ValueError: array must be of type Float64.

I’m not sure what you mean by “2.7 vpython”. Can you post the full URLs of the download links that you used for both Python and VPython? For example, the current VPython download page lists the following installs:

Python: http://www.python.org/ftp/python/2.7.5/python-2.7.5.msi

VPython: http://sourceforge.net/projects/vpythonwx/files/6.05-release/VPython-Win-32-Py2.7-6.05.exe/download

Is this what you installed?

Yes, I installed the links you sent.

Ok, I tried this out with the latest version (2.7.5/6.05) and was able to reproduce the problem you are seeing. There appears to be a bug in the dot() function, either in VPython or the underlying Numpy, I’m not sure, that complains about the int32 data type of the vector operands.

Fortunately, this is easy to workaround: replace the dot() expression with the following:

sum(q[:6] * (3 ** arange(5, -1, -1)))

I verified that with this change the rest of the code will run to completion (including the rubik2_gui).

Thanks for pointing this out. I will make this change in the archived code as well.

I installed python 2.7 and 2.7 vpython, when running rubik2.py happens the following error

Computing cube graph …

Traceback (most recent call last):

File “D: \ rubik2 \ rubik2.py”, line 101

cubegraph = g ()

File “D: \ rubik2 \ rubik2.py”, line 73, in cubegraph

g.append ([packcube (movecube (cube, move)) is moving in cubemoves])

File “D: \ rubik2 \ rubik2.py”, line 40, in packcube

rankperm return (p) * 6 ** 3 + dot (q [: 6] 3 ** arange (5, -1, -1))

ValueError: array must be of type Float64.

hello I corrected the error, but not left running program, rubik_gui worked perfectly.

I ask, how long it takes to calculate the graph of the cube?, and what happens when it finishes calculating?

It takes about 20-30 minutes to compute the cube graph. Once it’s complete, it takes just a few additional seconds to compute a shortest path spanning tree rooted at the vertex corresponding to the solved configuration. This tree is then saved (in “predecessor vector” form) to the file rubik2.dat.

This file can be used to solve any configuration of the cube, by “walking up the tree” from the current configuration to its parent, until you reach the root. See the rubik2_gui.py program for an example; pressing the ‘s’ key makes a single move up the tree; that is, it makes a single move on the shortest path to the solved cube.

ok, I opened the file in Notepad rukid.dat, it has several numbers 4-7 digit numbers that would be movements?, if not, have the possibility to save the combinations and movements x, X, y, Y, z, Z.

generate movements so I can solve the cube manually

There are 3,674,160 numbers in the .dat file, call them p[0], p[1], p[2], etc., one for each vertex in the cube graph– that is, one for each configuration of the cube. Each number p[i] is between 0 and 3,674,159, indicating the *parent* of vertex i in the shortest path spanning tree rooted at the vertex corresponding to the solved configuration.

The “movements” correspond to traversing an edge in the cube graph. To figure out which of the 6 possible movements corresponds to the parent vertex, check out the code: it just tries all 6 rotations, looking for which one yields the parent representation.

Pingback: Train tracks and graph theory | Possibly Wrong

Hallo,

This is quite an old post, but I found it very interesting.

How did you label your cube?

I do not understand the orientation part of your program.

Every time if you rotate a face, all four cubies’ orientations are changed.

It is confusing. I’ve seen some other implementation (3x3x3), there in case of some move the orientation does not change.

BR,

K

I’m not sure I understand your question well enough to provide a clear answer. By “label the cube,” consider positioning the cube so that the cubies are centered at (0/1, 0/1, 0/1). Then fix the cubie at the origin, and number the remaining 7 cubies 0 through 6 in the order (1,0,0), (0,1,0), (1,1,0), (0,0,1), (1,0,1), (0,1,1), (1,1,1). Then the permutation part of the cube state indicates how the cubies are permuted from the solved state. (Add a print(cube) statement at the end of the if: block in the while True: loop in rubik2_gui.py to see how this works.)