# rubik.py
# Author: Ronald L. Rivest
# Last updated: November 6, 2007
#
# Routines to work with Rubik's 2x2x2 cube
import sys
import time
"""
We'll call the six sides, as usual:
Front Back Up Down Left Right
or F, B, U, D, L, R.
Permutations:
We'll number the cubie positions starting
at 0, front to back, up to down, left to right.
We give an alphabetic name to the cubies as well,
by listing the faces it contains, starting with
F or B, in clockwise order (looking in from outside).
0th cubie = FLU
1st cubie = FUR
2nd cubie = FDL
3rd cubie = FRD
4th cubie = BUL
5th cubie = BRU
6th cubie = BLD
7th cubie = BDR
Each cubie has three faces, so we have 24 face
positions. We'll label them as 0 to 23, but also
with a 3-letter name that specifies the name
of the cubie it is on, cyclically rotated to
put the name of the face first (so cubie FLU
has faces flu, luf, and ufl, on sides F, L,
and U, respectively). We'll use lower case
here for clarity. Here are the face names,
written as variables for later convenience.
We also save each number in a second variable,
where the positions are replaced by the colors that
would be there if the cube were solved and had its
white-red-green cubie in position 7, with white
# facing down.
"""
# flu refers to the front face (because f is first) of the cubie that
# has a front face, a left face, and an upper face.
# yob refers to the colors yellow, orange, blue that are on the
# respective faces if the cube is in the solved position.
yob = flu = 0 # (0-th cubie; front face)
oby = luf = 1 # (0-th cubie; left face)
byo = ufl = 2 # (0-th cubie; up face)
ybr = fur = 3 # (1-st cubie; front face)
bry = urf = 4 # (1-st cubie; up face)
ryb = rfu = 5 # (1-st cubie; right face)
ywo = fdl = 6 # (2-nd cubie; front face)
woy = dlf = 7 # (2-nd cubie; down face)
oyw = lfd = 8 # (2-nd cubie; left face)
yrw = frd = 9 # (3-rd cubie; front face)
rwy = rdf = 10 # (3-rd cubie; right face)
wyr = dfr = 11 # (3-rd cubie; down face)
gbo = bul = 12 # (4-th cubie; back face)
bog = ulb = 13 # (4-th cubie; up face)
ogb = lbu = 14 # (4-th cubie; left face)
grb = bru = 15 # (5-th cubie; back face)
rbg = rub = 16 # (5-th cubie; right face)
bgr = ubr = 17 # (5-th cubie; up face)
gow = bld = 18 # (6-th cubie; back face)
owg = ldb = 19 # (6-th cubie; left face)
wgo = dbl = 20 # (6-th cubie; down face)
gwr = bdr = 21 # (7-th cubie; back face)
wrg = drb = 22 # (7-th cubie; down face)
rgw = rbd = 23 # (7-th cubie; right face)
"""
A permutation p on 0,1,...,n-1 is represented as
a list of length n-1. p[i] = j means of course
that p maps i to j.
When operating on a list c (e.g. a list of length
24 of colors), then p * c
is the rearranged list of colors:
(p * c)[i] = c[p[i]] for all i
Thus, p[i] is the location of where the color of
position i will come from; p[i] = j means that
the color at position j moves to position i.
"""
####################################################
### Permutation operations
####################################################
def perm_apply(perm, position):
"""
Apply permutation perm to a list position (e.g. of faces).
Face in position p[i] moves to position i.
"""
return tuple([position[i] for i in perm])
def perm_inverse(p):
"""
Return the inverse of permutation p.
"""
n = len(p)
q = [0]*n
for i in xrange(n):
q[p[i]] = i
return tuple(q)
def perm_to_string(p):
"""
Convert p to string, slightly more compact
than list printing.
"""
s = "("
for x in p: s = s + "%2d "%x
s += ")"
return s
###################################################
### Make standard permutations of faces
###################################################
# Identity: equal to (0, 1, 2, ..., 23).
I = (flu, luf, ufl, fur, urf, rfu, fdl, dlf, lfd, frd, rdf, dfr,
bul, ulb, lbu, bru, rub, ubr, bld, ldb, dbl, bdr, drb, rbd)
"""
When any of the following Rubik's cube permutations are applied, the
three faces on a cubie naturally stay together:
{0,1,2}, {3,4,5}, ..., {21,22,23}.
"""
# Front face rotated clockwise.
F = (fdl, dlf, lfd, flu, luf, ufl, frd, rdf, dfr, fur, urf, rfu,
bul, ulb, lbu, bru, rub, ubr, bld, ldb, dbl, bdr, drb, rbd)
# Front face rotated counter-clockwise.
Fi = perm_inverse(F)
# Left face rotated clockwise.
L = (ulb, lbu, bul, fur, urf, rfu, ufl, flu, luf, frd, rdf, dfr,
dbl, bld, ldb, bru, rub, ubr, dlf, lfd, fdl, bdr, drb, rbd)
# Left face rotated counter-clockwise.
Li = perm_inverse(L)
# Upper face rotated clockwise.
U = (rfu, fur, urf, rub, ubr, bru, fdl, dlf, lfd, frd, rdf, dfr,
luf, ufl, flu, lbu, bul, ulb, bld, ldb, dbl, bdr, drb, rbd)
# Upper face rotated counter-clockwise.
Ui = perm_inverse(U)
# All 6 possible moves (assuming that the lower-bottom-right cubie
# stays fixed).
quarter_twists = (F, Fi, L, Li, U, Ui)
quarter_twists_names = {}
quarter_twists_names[F] = 'F'
quarter_twists_names[Fi] = 'Fi'
quarter_twists_names[L] = 'L'
quarter_twists_names[Li] = 'Li'
quarter_twists_names[U] = 'U'
quarter_twists_names[Ui] = 'Ui'
###############################################
### Now do BFS
###############################################
def input_configuration():
position = [-1]*24
"""
Prompts a user to input the current configuration of the cube, and
translates that into a permutation.
"""
cubie = raw_input("""\
Look for the cubie that has the label: ICE RUBIK'S CUBE. The label
should be on a white face, and the cubie should also have green
and red faces. Put this cubie in the lower-back-right corner with
the label facing down. We will call this cubie #7.
Now look at the cubie in the upper-front-left corner. We will call
this cubie #0. Starting with its front face, and going clockwise,
input the colors of the faces (e.g. yob, if the colors are yellow,
orange, and blue):
cubie #0: """)
position[0] = eval(cubie)
position[1] = eval(cubie[1:] + cubie[0])
position[2] = eval(cubie[2] + cubie[:2])
cubie = raw_input("""
Now enter cubie #1, which is to the right of cubie #0, again
starting with the front face and going clockwise:
cubie #1: """)
position[3] = eval(cubie)
position[4] = eval(cubie[1:] + cubie[0])
position[5] = eval(cubie[2] + cubie[:2])
cubie = raw_input("""
Now enter cubie #2, which is beneath cubie #0:
cubie #2: """)
position[6] = eval(cubie)
position[7] = eval(cubie[1:] + cubie[0])
position[8] = eval(cubie[2] + cubie[:2])
cubie = raw_input("""
Now enter cubie #3, to the right of cubie #2:
cubie #3: """)
position[9] = eval(cubie)
position[10] = eval(cubie[1:] + cubie[0])
position[11] = eval(cubie[2] + cubie[:2])
cubie = raw_input("""
Now enter cubie #4, which is behind cubie #0. Start with the back
face, and go clockwise:
cubie #4: """)
position[12] = eval(cubie)
position[13] = eval(cubie[1:] + cubie[0])
position[14] = eval(cubie[2] + cubie[:2])
cubie = raw_input("""
Now enter cubie #5, which is to the right of cubie #4:
cubie #5: """)
position[15] = eval(cubie)
position[16] = eval(cubie[1:] + cubie[0])
position[17] = eval(cubie[2] + cubie[:2])
cubie = raw_input("""
Now enter cubie #6, which is beneath cubie #4:
cubie #6: """)
position[18] = eval(cubie)
position[19] = eval(cubie[1:] + cubie[0])
position[20] = eval(cubie[2] + cubie[:2])
print """We already know cubie #7, so we're done."""
cubie = 'gwr'
position[21] = eval(cubie)
position[22] = eval(cubie[1:] + cubie[0])
position[23] = eval(cubie[2] + cubie[:2])
return tuple(position)
def count_repetitive_twists(moves):
"""
When you apply the same twists to a cube over and over again, the
cube will eventually return to its original position. This applies
each move in moves repeatedly, until the cube returns to its
original position, and counts the length of the cycle.
"""
current_position = I
for count in xrange(1, 100000):
for move in moves:
current_position = perm_apply(move, current_position)
if(current_position == I):
return count
def rubik_bfs(moves, level):
"""
Using BFS, returns the number of cube configurations that are
exactly a given number of levels away from the starting position
(I).
"""
return 'NOT_IMPLEMENTED' # For moves=quarter_twists and level=1,
# this returns 6
def shortest_path(start_position, end_position):
"""
Using 2-way BFS, finds the shortest path from start_position to
end_position.
Assumes the quarter_twists move set.
"""
return 'NOT_IMPLEMENTED' # If the start position is 2 twists away
# from the end position, this might
# return ['F', 'L']
# Use the dictionary quarter_twists_names
# to get the names for the rotations
# you use.
if __name__ == "__main__":
print perm_apply(F, I)
input_configuration()
#print count_repetitive_twists((F, L))
#import profile
#profile.run("rubik_bfs(quarter_twists, 1)", sort=1)