Rubik's Cube in a C# Console Program

• Download demo - 35.79 KB
• Download source - 11.02 KB

Introduction

I have been playing Rubik's cube for a long time, but I couldn't solve a single one until recently. After searching for a solution on websites, I managed to get to the last layer. I often make a mistake and then I get lost. So, I decided to write this program to help me keep track of the moves.

Design Choices

UI Program or Console Program

I started with a UI program, but I found that it needs many inputs, such as which face to rotate, and for how many degrees, etc. It would need many buttons or menus for a UI program. I wanted to keep the move history so that I can scroll up and down to check the states that I have visited. The Console program automatically supports scroll up and down. Finally, it is much easier to implement a Console program than a UI program. So, I decided to write the game as a Console program.

Draw the Cube in 2D or 3D Graph

The Rubik's Cube is a 3D game. But, the disadvantage of a 3D implementation is that I cannot see all the six faces at the same time. So, I present the Cube in a 2D graph. A cube has six faces, let's name them 0-5.

• 0 F = front face
• 1 R = right face
• 2 U = up face
• 3 L = left face
• 4 D = down face
• 5 B = back face

3D presentation of a Cube:
               ___
              /2 /|
             /__/ | 5
            |   |1|
          3 | 0 | /
            |___|/
              4
2D presentation of a Cube:
         ___
        |   |
        | 2 |
     ___|___|___
    |   |   |   |
    | 3 | 0 | 1 |
    |___|___|___|
        |   |
        | 4 |
        |___|
        |   |
        | 5 |
        |___|

The screenshot of the program looks like this:

Note that each face has 9 cubies. The center cubie has only one number, which represents its color. The edge cubie has two numbers. The first number is its color; the second number is its neighbor's color. The corner cubie has three numbers. The first is its own color, followed by its two neighbor's colors.

Each cube has two extra attributes: step and path. The step is the number of moves to reach the state. The path is a string which records all the moves. It uses the notations explained below.

Notations of the Moves

I implemented all the moves described in Wikipedia. The full list is:

• F (Front): The side currently facing you
• B (Back): The side opposite the front
• U (Up): The side above or on top of the front side
• D (Down): The side opposite the top, underneath the Cube
• L (Left): The side directly to the left of the front
• R (Right): The side directly to the right of the front
• f (Front two layers): The side facing you and the corresponding middle layer
• b (Back two layers): The side opposite the front and the corresponding middle layer
• u (Up two layers): The top side and the corresponding middle layer
• d (Down two layers): The bottom layer and the corresponding middle layer
• l (Left two layers): The side to the left of the front and the corresponding middle layer
• r (Right two layers): The side to the right of the front and the corresponding middle layer
• x (rotate): Rotate the Cube up
• y (rotate): Rotate the Cube counter-clockwise
• z (rotate): Rotate the Cube clockwise

I found that all the solutions on the web are using just one layer moves. The x, y, z moves are very useful when I apply the techniques from Beginner's solution.

Features

Scroll Up and Down the History

The most important purpose of this program is to list the history of the moves. It gives me a step by step guide of the moves. Console programs automatically support scroll up and down. After many "undo" operations, it might become difficult to track the history. Typing the command "history" will print out all the moves so far.

Detect a Duplicate Cube State

It is very frustrating when I run into a loop and keep repeating the same moves. So, I wrote the program to detect if I have visited a cube state already. It reports the old cube which I visited before, and rejects the new move.

Detect a Similar Cube State

If I make the moves x, y, or z (roll up/down the whole cube) moves, then the cube is in a different but similar state. The program warns me of the situation but accepts the move.

List of Interesting Patterns

I can set the start position to a super flip or other interesting patterns. I have also included the common solution steps from the Beginner's solution for practice. Type 'List' to get the whole list of pattern names, and then type the number of the pattern to set the initial Cube state. For example, 0 is the initial Cube state, 1 is super flip.

Reset to the Start Position

After making many moves, sometimes I would want to give up and start all over. Type 'Reset' to have a fresh restart.

Undo the Last Move

If I have made a wrong move, I can simply type 'undo' to revert the move.

Apply Multiple Moves at the Same Time

When I try to apply the moves from Beginner's solution, I often need to make multiple moves at the same time. For example, to permutate the last layer's edge, I would need 9 moves:

R2 U' F B' R2 F' B U' R2

Instead of typing 9 commands, I can simply type "apply R2 U' F B' R2 F' B U' R2".

Read a Cube from the Console

When I use the program to help me solve a cube, I need to input it into the program. Type "read" and then type the color of each face to input the Cube.

Design

The Cube class has six Faces. Each Face has nine Cubies. Each Cubie has two attributes: Position and Color. There are totally 18 one layer moves, 18 two layer moves, and 3 roll cube moves. Each Move object works on a Cube object. The relation of these classes looks like this:

There are helper classes, such as FaceLayout2D and FaceLayout3D, which describe the relations of faces in the Cube. The RubikPattern class records the interesting patterns. The CubeReader class helps input the state of a Cube into the program. The ConsoleColor helps setting background and foreground colors. The MoveHistory records all the steps we have made so far.

Implementation of Cube's Move

Although there are 39 different moves for the Cube, the only way to change a Cube's state is to rotate the cube. When we are rotating a face, we are actually rotating every cubie in the face. From the class diagram above, you can see that the Cube is an aggregation of smaller object in layers: Cube has Face, Face has Cubie, CubiePosition has FaceIndex. So, we just need to define the rotation in each layer. We first find out how to rotate the front face clockwise 90 degree.

Front Face Rotate Clockwise 90 Degree

The name of this move is "F". In order to rotate a Face, we need to implement the rotation of each Cubie on the face. Note that rotating the front face won't affect the position of back face. So, we only need to examine the right(1), up(2), left(3), and down(4) faces after the rotation. In the below graph, after we clockwise rotate 90 degree, we'll transform:

     ___
    |   |
    | 2 |
 ___|___|___
|   |   |   |
| 3 | 0 | 1 |
|___|___|___|
    |   |
    | 4 |
    |___|

into:

     ___
    |   |
    | 3 |
 ___|___|___
|   |   |   |
| 4 | 0 | 2 |
|___|___|___|
    |   |
    | 1 |
    |___|

That is the foundation of all the rotation functions. We can implement the function as:

class Face{
public static sbyte RotateFrontClockwise90Degree(sbyte v)
{
    switch (v)
    {
        case Face.Front:
            return (sbyte)Face.Front;
        case Face.Right:
            return (sbyte)Face.Down;
        case Face.Down:
            return (sbyte)Face.Left;
        case Face.Left:
            return (sbyte)Face.Up;
        case Face.Up:
            return (sbyte)Face.Right;
        case Face.Back:
            return Face.Back;
        default:
            throw new ApplicationException("invalid input");
    }
}

Rotate of Cubie

In the beginning, I stored the Cubies as:

class Face{
Cubie[,] cubies=new Cubie[3,3];
}

But this is not the natural way to locate a cubie. When a Face is rotated from Front to Back, the cubies[0,0] would become cubies[2,2], which makes it difficult to track. From the web, I learned that the easiest way to address a cubie is by its color. So, in the code, I also address the Cubie by its color. The class CubiePosition and CubieColor both have three numbers which are the original color in the Cube's initial state. They are the same in the beginning. When the Cube is rotated, the CubiePosition stays in the same Face, but the CubieColor might be moved to other Faces.

class CubiePosition{
sbyte a1, a2, a3
}
class CubieColor{
sbyte color, neighbor1, neibor3
}
class Cubie{
CubiePosition position;
CubieColor color;
}
class Face{
List<cubie> cubies;
}

The CubiePosition has 3 numbers: a1, a2, a3. where a1<=a2<=a3. If a1==a2==a3, then the cubie is in the center. If a1==a2<a3, then the cubie is on the Edge. If a1<a2<a3, then the cubie is on the corner. So, we can further implement the rotation of a Cubie:

class CubiePosition{
public void RotateFrontClockwise90Degree()
{
    a1 = Face.RotateFrontClockwise90Degree(a1);
    a2 = Face.RotateFrontClockwise90Degree(a2);
    a3 = Face.RotateFrontClockwise90Degree(a3);
    AdjustOrder();//make sure that a1<=a2<=a3
}
}

Rotate the Front Face

Now we can implement the rotation of Front Face:

class Face{
    public void RotateFrontClockwise90Degree(){
        foreach (Cubie cubie in cubies){
            cubie.position.RotateFrontClockwise90Degree();
        }
    }
}

Rotate the Cube

Finally, we can implement the rotation of a Cube. It has two steps. First, it rotates the cubies on the front face. Second, it rotates 3 cubies on the right, up, left, and down faces.

class Cube{
public void RotateFrontClockwise90Degree()
{
    //rotate the front side
    faces[Face.Front].RotateFrontClockwise90Degree();
    //For the right, up, left, and down side, we need to rotate one row that is 
    //close to the front side
    //we start at the up side. The three cubies are the [up, front, {left/front/right}]
    foreach (sbyte side in new sbyte[] { Face.Left, Face.Front, Face.Right })
    {
        sbyte currentFace = Face.Up;
        sbyte currentPosition = side;
        CubieColor saved = faces[currentFace][currentFace, Face.Front, currentPosition];
        for (int i = 0; i < 4; i++)
        {
            // go counter-clockwise to update each value
            sbyte nextFace = Face.RotateFrontCounterClockwise90Degree(currentFace);
            sbyte nextPosition = 
		Face.RotateFrontCounterClockwise90Degree(currentPosition);
            if (i == 3)
            {
                faces[currentFace][currentFace, Face.Front, currentPosition] = saved;
            }
            else
            {
                faces[currentFace][currentFace, Face.Front, currentPosition] = 
			faces[nextFace][nextFace, Face.Front, nextPosition];
            }
            currentFace = nextFace;
            currentPosition = nextPosition;
        }
    }
}
}

Other Two Rotations for Front Face

After we implement move F(Front Face clockwise 90 degree), the other two rotations on Front Face are very simple. F2 (Front Face clockwise 180 degree) is to apply F twice. F' (Front Face counter clockwise 90 degree) is to apply F 3 times.

Rotations for Other Faces

Because Rubik's cube is symmetric, the other rotations are exactly the same. In order to avoid duplicate code, we can simply map the specified face to front side, perform the specified rotation, and then map the face back.

class Cube{
private static void RotateFace(Cube s, int n, sbyte face)
{
    Debug.Assert(n < 4);
    Debug.Assert(face < 6);
    s.MapFrontFrom(face);
    RotateFront(s, n);
    s.MapFrontTo(face);
}
}

Mapping Between Cube Faces

The mapping between faces is very straightforward. In order to map Right Face to Front, we simply expand the 3D Cube with Face 1 at the center.

3D
                ___
               /2 /|
              /__/ | 5
             |   |1|
           3 | 0 | /
             |___|/
               4

If we open them into 2 dimensions with Face 0 in the center:

     ___
    |   |
    | 2 |
 ___|___|___
|   |   |   |
| 3 | 0 | 1 |
|___|___|___|
    |   |
    | 4 |
    |___|
    |   |
    | 5 |
    |___|

If we open the cube into 2 dimensions with Face 1 in the center:

     ___
    |   |
    | 0 |
 ___|___|___
|   |   |   |
| 4 | 1 | 2 |
|___|___|___|
    |   |
    | 5 |
    |___|
    |   |
    | 3 |
    |___|

So, to map Right to Front (Function MapFrontFrom), we just need to return this mapping:

1->0, 2->1, 0->2, 4->3, 5->4, 3->5

To map Front to Right (Function MapFrontTo), we just need to return this mapping:

0->1, 1->2, 2->0, 3->4, 4->5, 5->3

Note that this map is not unique. We have 4 ways to map Right face to Front face. Any of them will work. We record this information in class FaceLayout3D:

class FaceLayout3D{
public static FaceLayout3D[] face3DLayouts;
static FaceLayout3D()
{
    face3DLayouts = new FaceLayout3D[6];
    face3DLayouts[0] = new FaceLayout3D(0, 1, 2, 3, 4, 5);
    face3DLayouts[1] = new FaceLayout3D(1, 2, 0, 4, 5, 3);
    // reset maps...
}

With the help of this matrix, we can implement the MapFrontFrom and MapFrontTo function like this:

class FaceLayout3D{
sbyte[] order;
sbyte[] reverseOrder;
private FaceLayout3D(sbyte a1, sbyte a2, sbyte a3, sbyte a4, sbyte a5, sbyte a6)
{
    order = new sbyte[6] { a1, a2, a3, a4, a5, a6 };
    reverseOrder = new sbyte[6];
    for (sbyte i = 0; i < 6; i++)
    {
        for (sbyte j = 0; j < 6; j++)
        {
            if (order[j] == i)
            {
                reverseOrder[i] = j;
            }
        }
    }
}

public static sbyte MapFrontFrom(sbyte side, sbyte facelet)
{
    FaceLayout3D r = face3DLayouts[side];
    // order[i] - > i
    return r.reverseOrder[facelet];
}

public static sbyte MapFrontTo(sbyte side, sbyte facelet)
{
    FaceLayout3D r = face3DLayouts[side];
    // i - > order[i]
    return r.order[facelet];
}
}

Because the Cube's aggregation nature, I have to implement the MapFrontTo and MapFrontFrom in CubiePosition, Face, and Cube classes. But the implementation is straightforward.

The function AdjustFaces() is to make sure that the Front Face is faces[0], and Right Face is faces[1], etc.

C# Features Used in this Program

Interop to Set Console Color

C# doesn't have support for Console Colors. We can use interop to call the Windows API:

CONSOLE_SCREEN_BUFFER_INFO consoleScreenBufferInfo;
GetConsoleScreenBufferInfo(hConsole, out consoleScreenBufferInfo);
this.oldTextAttributes = consoleScreenBufferInfo.wAttributes;
int wTextAttributes = (this.oldTextAttributes & ~0xFF) | color;
SetConsoleTextAttribute(hConsole, wTextAttributes);

Keyword "using" to Call Dispose()

To make sure that we reset the Console color, we use the "using" statement to reset the color:

using (new ConsoleColor(color)
{
    Console.Write("{0}", c);
}

Lambda Expression

Lambda makes it easy to write anonymous functions.

delegate void MoveFunction(Cube s);
MoveFunction action;
static void AddMove(string name, MoveFunction action)
{
    allMoves.Add(name, new Move(name, action));
}
//Define all the moves:
    AddMove("F", s => RotateFront(s, 1));
    AddMove("F2", s => RotateFront(s, 2));
    AddMove("F'", s => RotateFront(s, 3));

This is much better than the below method:

if(move=="F") RotateFront(s,1) else if(move=="F2") ...

For example, we can use the Dictionary to check whether a move is valid:

public static bool IsValidMove(string move)
{
    return allMoves.ContainsKey(move);
}

Using the Code

I used VS2008 to compile the program. You might need to install the .NET runtime to run the compiled binaries. The program sets console colors. If you stop the program with 'Ctrl-C', you might need to type 'Color' to reset your console color. If your cube has a different color than my cube, you can change the colors in the program. You'll need to use AddFaceColorMap in the program. The current map is:

AddFaceColorMap(Front, "Front", ConsoleColor.BackGroundColor.Grey, "w");
AddFaceColorMap(Right, "Right", ConsoleColor.BackGroundColor.Yellow, "y");
AddFaceColorMap(Up, "Up", ConsoleColor.BackGroundColor.Magenta, "p");
AddFaceColorMap(Left, "Left", ConsoleColor.BackGroundColor.Green, "g");
AddFaceColorMap(Down, "Down", ConsoleColor.BackGroundColor.Red, "r");
AddFaceColorMap(Back, "Back", ConsoleColor.BackGroundColor.Blue, "b");

Conclusion

With the help of this program, I finally solved my Rubik's Cube for the first time. I found that the real Rubik's Cube is interesting to play with, but it is very difficult to track the steps. This computer program helps to try out various steps and keep track of the moves.

I tried to play the computer game directly, but I found that it is very boring without a real Rubik's Cube. I guess that the challenge is exactly the reason why the Rubik's Cube is so much fun.

History

• 22^nd March, 2009: Initial post
• 25^th March, 2009: Updated article
• Added explanation on the algorithm of Cube Rotation
• Added list of C# features that I used in the program