Thursday, November 22, 2012

Solving the Rubik's Cube

I've been reading and practicing the rubik's cube for the past few years. When I was in grade school the rubik's cube had just come out. And a number of students could actually solve the cube. Which I thought was amazing, but I had never bothered to learn how to do so. What I find interesting is that a 3x3x3 cube has 43,252,003,274,489,856,000 possible configurations! Which is a good example of the almost infinite complexity that is the most basic structures we have all around us.

Over the Thanksgiving break I thought I'd write a program that could receive input of an unsolved Rubik Cube and output the moves required to solve the cube. I was thinking of various data structures to store the cube in a straight forward way. Here is what I was originally thinking for storing the pieces and positions:

public enum Cubies {
        WBO, WO, WOG, WG, WGR, WR, WRB, WB,
        BO, OG, GR, RB,
        YBO, YO, YOG, YG, YGR, YR, YRB, YB
    }

public enum Positions {
        WLR, WR, WRR, WML, WMR, WFL, WFM, WFR,
        BRE, BOE, RGE, OGE,
        YLR, YR, YRR, YML, YMR, YFL, YFM, YFR
    }

Here W=white, R=right/red, L=left, M=middle, F=front, B=blue,O=orange,G=green,Y=yellow

Then just have the actual cube stored as an array of strings that contain the actual color of each square. After struggling for a few hours on writing methods for createCube, printCube, TwistCube(Side), etc. I thought I'd google the code and found CubeTwister:

http://www.randelshofer.ch/cubetwister/

Which shows someone has been doing their homework in regard how to store the Rubik's Cube as a data structure. If you look at the ch.randelshofer.rubik.AbstractCube class you can see that the cube is stored as a number of int arrays. Here is one example:

    protected final static int[][] CORNER_TO_FACE_MAP = {
        {1, 0, 2}, // urf
        {4, 2, 0}, // dfr
        {1, 5, 0}, // ubr
        {4, 0, 5}, // drb
        {1, 3, 5}, // ulb
        {4, 5, 3}, // dbl
        {1, 2, 3}, // ufl
        {4, 3, 2}, // dlf
    };

0=right, 1=up, 2=front, 3=left, 4=down, 5=back

One of the most interesting integer arrays is a four dimensional


     Corner swipe table.
     First dimension: side part index.
     Second dimension: orientation.
     Third dimension: swipe direction
     Fourth dimension: axis, layermask, angle
   
                 +---+---+---+
                 |4.0|   |2.0|
                 +---     ---+
                 |     1     |
                 +---     ---+
                 |6.0|   |0.0|
     +---+---+---+---+---+---+---+---+---+---+---+---+
     |4.1|   |6.2|6.1|   |0.2|0.1|   |2.2|2.1|   |4.2|
     +---     ---+---     ---+---    +---+---     ---+
     |     3     |     2     |     0     |     5     |
     +---     ---+---     ---+---    +---+---     ---+
     |5.2|   |7.1|7.2|   |1.1|1.2|   |3.1|3.2|   |5.1|
     +---+---+---+---+---+---+---+---+---+---+---+---+
                 |7.0|   |1.0|
                 +---     ---+
                 |     4     |
                 +---     ---+
                 |5.0|   |3.0|
                 +---+---+---+

No comments: