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.

**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.)

Hi,

I really like your post and this representation of the state is super neat!

But I have some questions as well:

1. For the 6 hard-coded moves, I understand \pi, but I am really confused about q:

1) why q in the solved state is zeros(7)?

2) for example, for move X, why its corresponding q is [1, 0, 1, 0, 2, 0, 2]?

3) how does “(cq[mp] + mq) % 3” work exactly in move_cube()?

2. could you also explain why “the orientations of any 6 cubies determine the remaining orientation. We can impose this constraint by requiring the sum modulo 3 of elements of q to be zero.”?

Is there a proof of this?

Thank you!

First, note that a state of the cube is represented as a tuple (cp, cq), where the permutation cp describes how the cubies have been permuted from the solved state, and the vector cq describes the orientations of each of the cubies.

We represent a move in the same way as (mp, mq), where mp describes how we permute the cubies with a single face rotation, so that cp[mp] is the resulting new arrangement of the cubies after applying the move. To determine the new *orientations* of the cubies, we first apply the same permutation to the initial orientations via cq[mp], then add the *change* in orientations resulting from the move via +mq. The mod 3 simply constrains the results to be in {0,1,2}.

So, how do we represent those changes in orientation? We actually have some freedom in choosing how we do this; that is, there are other choices of six mq vectors for the six face rotations that work. Having come back to look at this again 8 years later, it might be easier to visualize a different choice than the one that I used (more on this later):

Consider the cube to be positioned so that the cube is at the origin, with the front (F), right (R), and up (U) faces in the +x, +y, and +z-axis directions, respectively, as shown here, where we are “holding” the cube by the cubie that we can’t see located at (-1,-1,-1), and the remaining seven non-fixed cubies are numbered as shown.

Each non-fixed cubie could be in one of three different orientations; we need a way to encode these three possibilities. To do this, first note that each cubie has exactly one face that is either green (on the F[ront] face when solved) or blue (on the B[ack] face when solved). No matter where a particular cubie is located, let’s denote its orientation 0 if its green-or-blue face is currently on the F-or-B face, or +1 if it has been rotated counterclockwise (about a ray from the origin through the cubie) from that “0” orientation, or -1 (or +2 since we are working mod 3) if it has been rotated clockwise from that “0” orientation.

Then we can compute what the mq vector should be for each of the six possible face rotations: for both X+ and X- rotations, the mq vector is (0,0,0,0,0,0,0). For both Y+ and Y- rotations, the mq vector is (0,2,1,0,0,1,2), and for both Z+ and Z- rotations, the mq vector is (0,0,0,1,2,2,1).

You can verify that the code works with these mq vectors in the same way as the original code. (I originally enumerated all possible valid sets of mq vectors, and chose a set that minimized the number of non-zero vectors. In hindsight I think the above is much easier to explain :). Also, having settled on this particular choice of mq vectors, we can verify that any single face rotation preserves the invariant that the sum of orientations is zero mod 3.

Thank you for your reply.

I still have some questions:

1.

Could you elaborate on “we first apply the same permutation to the initial orientations via cq[mp], then add the *change* in orientations resulting from the move via +mq”?

Why does this work exactly? (Thanks for your patience, I’m really confused about why this works.)

2.

I can understand your new choice of the six mq vectors, but originally why did you want to minimize the number of non-zero vectors?

3.

From your previous reply (May 16, 2016 at 7:33 pm), if the coordinates of the seven visible cubies are: (1,0,0), (0,1,0), (1,1,0), (0,0,1), (1,0,1), (0,1,1), (1,1,1), then should the invisible cube be located at (0,0,0) instead of (-1,-1,-1)?

4.

Currently, you are not considering spatial rotations (by fixing one cubie, only using six moves); if you are considering spatial rotations (not fixing any cubie, using twelve moves), is it only going to change p from S7 to S8, and q from 7-vector to 8-vector with element in GF(3)?

Thanks again!

@br8mile, to answer your questions:

1. I might need some more detail on exactly which part(s) of this are confusing. Is it the permutation (rotating a face moves four of the cubies, while keeping the other four fixed, this action can be realized with Numpy array indexing, as in cp[mp] to move the cubes themselves, and cq[mp] to move our record of their orientations) or the vector addition to “rotate” the orientations?

2. No useful reason at all :). That is, there are a lot of options– I started by generating all 3^6=729 possible sets of six mq vectors– and I didn’t want to make an arbitrary choice (although any of them will work). And reviewing my code more closely, I see that I misspoke in my earlier comment: the set in rubik.py doesn’t minimize the number of non-zero entries (if anything, it non-uniquely realizes a *maximum*), instead it is the lexicographically last in the sorted list of all 729 possible sets.

3. This was an attempt to be clear in two different contexts, and I ended up being confusing in both :). In the first comment from 2016, I’m trying to justify the 0-through-7 numbering of the cubies, where you are correct that the hidden/fixed cubie is at (0,0,0). With this labeling we can “read” each cubie index 0 through 7 as a binary number obtained by writing the coordinates zyx.

But in this more recent comment from last week, my intent was instead to describe the action of rotating the faces, so I “shifted” and scaled the cube so that the face rotations are about the coordinate axes. That is, the origin is at the very center of the cube, each cubie is 2×2, so that the coordinates of the centers of the cubies are (+/-1, +/-1, +/-1).

4. You could do this, but then there would no longer be a one-to-one correspondence between permutations and *distinct* cube states. That is, orienting the cube as described in my previous comment, there is no need to *separately* represent the face turns B+, B-, L+, L-, D+, D-, because these moves are *equivalent* to (i.e., they yield the same effect on the cube state as) F+, F-, R+, R-, U+, U-, respectively. (Note that this is only true for the 2x2x2 cube; we actually need those additional moves for the 3x3x3 cube to realize all possible cube states.)

Happy new year!

Thanks for the explanation for 2, 3, 4.

My confusion for 1 is not related to the implementation, just conceptually, how does “(cq[mp] + mq) % 3” correctly update the orientation of each cubie?

I understand moving our record of their orientations is achieved by cq[mp], but why does the vector addition (+mq mod 3) work?

Thank you!

I suppose we should start with the description of the *representation* of the orientations in my comment of 12 December (starting with, “Each non-fixed cubie could be in one of three different orientations; we need a way to encode…”). If we understand this representation, then verify that for the initial solved state of the cube, each of the cubies is in the “zero” orientation.

Now consider a +X rotation, for example, when applied to that initial solved state. Recompute the encoded orientations of each of the cubies, and verify that they are unchanged (i.e., they are still all zero). Similarly, a -X rotation also leaved the encoding of the orientations unchanged.

However, for each of the other four quarter turn moves (always starting from the initial solved state), some orientation codes *will* change, to the (appropriately permuted) values described in the penultimate paragraph of the 12 December comment.

Now… instead of starting from the solved state, scramble the cube, and record the (codes for the) orientations of the cubies; call this vector q. Then, for each of the six possible moves, apply the move, inspect the cube, and write down the updated vector of encoded orientations, call this q2. The key observation is that the vector *difference* q2-q[p] (call this mq) for a given move is always the same, independent of the starting state of the cube to which you applied the move. That is, no matter what state of the cube we are in (solved or scrambled), we can compute the new vector of encoded orientations resulting from a move as q2=q[p]+mq.

I understand the representation and I can verify that applying the hard-coded moves to the solved state correctly updates the vector q.

My confusion is still about in general (not just from the solved state) why “(cq[mp] + mq) % 3” correctly updates cq? (could you elaborate on the “key observation” mentioned in the latest comment?)

Is there a proof for why “(cq[mp] + mq) % 3” works?

Thanks again!

I plan to post a new article shortly that will hopefully explain this in more detail.

Pingback: Solving the 2x2x2 Rubik’s cube (revisited) | Possibly Wrong