A simple rubik's cube solver I made back in college
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
CubeProblem.py
JCube
corners.cube
cube.py
readme
scrambled.cube
search.py
solved.cube
utils.py

readme

Notations used and other comments:
Colors: I use the standard Rubik's cube colors of white, blue, green, red, yellow, and orange.

Each of the six sides of the cube are labeled with one of the following names: front, back, up, down, left, right.

Face->color mappings
front:red
back: orange
up: white
down: blue
left: green
right: yellow

Axes:
My representation uses a right-handed coordinate system with the X axis in the direction of the right (yellow) face, the Y axis in the direction of the up (white) face, and the Z axis in the direction of the back (orange) face.

Each face is stored as a 3x3 matrix of the first letter of each color on each square of that face.

To find the orientation of a face used in my representation follow these steps:
1.) Look directly at the front face (red), and position the up (white), face on top so that the Y axis is pointing up and the Z axis is pointing right. This is the orientation used for the front side.
2.) To find the left, right, or back orientations, start at the correct orientation for the front face. Rotate the cube about the Y axis so that the desired face is in view. This is the orientation used for each of those sides.
3.) To find the up face orientaton, start at the correct orientation for the front face. Now rotate the cube about the X axis so that the top face is now in front.
4.) To find the bottom face orientation, start at the correct orientation for the front face. Now rotate the cube about the X axis so that the bottom face is now in front.

Actions:
There are 18 moves and 6 rotations possible on a cube. They are listed below.

moves:
F: rotate the slice containing the front face clockwise 90 degrees.
F': rotate the slice containing the front face counter-clockwise 90 degrees.
B: rotate the slice containing the back face clockwise 90 degrees.
B': rotate the slice containing the back face counter-clockwise 90 degrees.
U: rotate the slice containing the up face clockwise 90 degrees.
U': rotate the slice containing the up face counter-clockwise 90 degrees.
D: rotate the slice containing the down face clockwise 90 degrees.
D': rotate the slice containing the down face counter-clockwise 90 degrees.
L: rotate the slice containing the left face clockwise 90 degrees.
L': rotate the slice containing the left face counter-clockwise 90 degrees.
R: rotate the slice containing the right face clockwise 90 degrees.
R': rotate the slice containing the right face counter-clockwise 90 degrees.
F2: perform F (or F') twice
B2: perform B (or B') twice
U2: perform U (or U') twice
D2: perform D (or D') twice
L2: perform L (or L') twice
R2: perform R (or R') twice

rotations:
x: Rotate the entire cube 90 degrees clockwise when looking at the X axis (right/yellow face).
x': Rotate the entire cube 90 degrees counter-clockwise when looking at the X axis (right/yellow face).
y: Rotate the entire cube 90 degrees clockwise when looking at the Y axis (top/white face).
y': Rotate the entire cube 90 degrees counter-clockwise when looking at the Y axis (top/white face).
z: Rotate the entire cube 90 degrees clockwise when looking at the Z axis (back/orange face).
z': Rotate the entire cube 90 degrees counter-clockwise when looking at the Z axis (back/orange face).

Screen display:
The cube is displayed on the screen in an unfolded state. The first row shows the top face. The second row shows the left, front, right, and back faces. Finally, the third row shows the bottom face. Enter commands to manipulate the cube. By default it is output using pretty colors, however chances are in different environments it will not appear correctly. If you wish to disable pretty printing, visit the prettyprint() method at the bottom of cube.py. Further instructions within that function will guide you on how to disable color output.

Program execution:
Simply run the JCube executable. ./JCube should work just fine

Loading files:
It is possible to load a cube state from a file. The load commmand will ask for a filename that contains a cube state. Currently only minimal error checking is performed. Several .cube files containing valid and interesting states are provided for your entertainment.

solver:
The solver is of course the most interesting part of this program. I created two heuristics, neither of which are particularly intellegent, admissible, or optimal. Both work well for cubes that are not well scrambled. Generally less than 5 moves generated by the scramble command will allow the solver to finish fairly quickly.
The first heuristic counts the number of facelets (elements of the face arrays) that are of the correct color, and divides it by a constant to make it closer to being admissible (this is reasonable since any move will affect several facelets). I believe, but am not totally sure, that this heuristic is a little bit faster, but not quite as good.
The second heuristic uses a very simplified version of the heuristic used by Richard Korf in http://www-compsci.swan.ac.uk/~csphil/CS335/korfrubik.pdf. It splits the process of solving the cube into first solving the corners, then 6 edges, then the other 6 edges. This is the heuristic used by default, since it seems to model the actual process of solving the cube a little better and has similar performance.
I did quite a bit of testing for the heuristics, so here are some interesting things. On my desktop at home and black.cse.msu.edu, the solver will generally check 1800-2200 states per second. With the branching factor of 18 coming from the number of possible moves, this leads to the following number of possible (non-unique) states to be considered for a given number of random moves:
2 moves:     324
3 moves:    5832
4 moves:  104976
5 moves: 1889568
Dividing those numbers by 2000 will give a fairly accurate upper bound for the running time of the solver. It also explans why well randomized cubes are rarely solved quickly.