ECE 462 Fall 2010,
Group Programming Assignment
Stage 1 (Java) Cube Operations
If you find any mistake in this page, please inform the instructor. Thank you.
Summary
The first stage asks you to develop a program that can rotate the faces in a 3x3x3 Rubik's cube.
In this class, you need to consider only a 3 x 3 x 3 cube. Do not worry about 4 x 4 x 4 nor 5 x 5 x 5 cubes.
State
The Rubik's Cube is a state machine. The cube has six faces and each face has nine squres. There are totally 54 squares and each square can be one of the six colors. The six colors are
- Yellow (Y)
- Red (R)
- Green (G)
- Orange (O)
- Blue (B)
- White (W)
The states encode the colors of the squares. The following is the initial state, when all 9 squares in each face are of the same color. The dashed lines are provided so that you can print the image, cut it, and glue it into a cube.
It is important to understand the center of the cube will never change. These six squares' colors are always Y, R, G, O, B, and W. The face with the yellow center is called face 1; the face with the red center is called face 2. The cube's state is represented by a string of the colors in the faces. The default state is represented as
| Face |
1 |
2 |
3 |
4 |
5
|
6 |
7 |
8 |
9 |
| 1 |
Y |
Y |
Y |
Y |
Y
|
Y |
Y |
Y |
Y |
| 2 |
R |
R |
R |
R |
R
|
R |
R |
R |
R |
| 3 |
G |
G |
G |
G |
G
|
G |
G |
G |
G |
| 4 |
O |
O |
O |
O |
O |
O |
O |
O |
O |
| 5 |
B |
B |
B |
B |
B |
B |
B |
B |
B |
| 6 |
W |
W |
W |
W |
W |
W |
W |
W |
W |
Please remember that the values in column 5 never change.
Default View
We use the centers of the faces to determine the default view:
- Yellow is at the center of the top face.
- Red is at the center of the front face.
- Green is at the center of the right face.
Three center are invisible:
- White is at the center of the bottom face.
- Blue is at the center of the left face.
- Orange is at the center of the back face.
Please pay attention to this 3-D view because a rotation command will change the three visible faces.
Axes
The Rubik's Cube is a 3-dimensional object so we have to define the three axes. We adopt the right-hand rule for the three axes.The following figure shows the three axes:
Operations
There are 18 possible operations (also called commands in this assignment), as defined in "Speedsolving the Cube" by Dan Harris. There are more operations in Harris' book but ECE 462 uses only 18 of them. These commands are organized into two groups.
- Rotate the whole cube. The cube can be rotated in one of the three axes (X, Y, or Z).
- Turn one of the six faces by 90 degrees. They are
- U: turning the top face
- D: turning the bottom face
- F: turning the front face
- B: turning the back face
- R: turning the right face
- L: turning the left face
The direction is clockwise 90 degrees facing the origin along an axis or the face to be turned. These are nine commands. There are nine corresponding commands for counterclockwise 90 degrees. They are expressed by adding ' after each turn; for example, X' means rotating counterclockwise about the X axis; U' means turning the top face counterclockwise 90 degrees. Thus, there are 18 different turns.
The following are some examples, each from the initial state and the default view. Each arrow represents the color at the center of the invisible face.
Orange appears at the top face after R' or L. Green appears at the front face after U or D'.
If multiple operations are applied, the order is from left to right. For example, FU means rurning the front face first and the turning the top face.
Rotations do not change the cube's state. However, a rotation followed by a turn is different from the turn without the rotation, for example, XU is different from U.
In general, these operations are not cumutative. XU is different from UX. RL is the same as LR though.
State Transitions
After defining the 18 operations, we can define the state machine of a Rubik's Cube. An operation may change the cube's state, as shown in the following figure.
After applying the F operation from the initial state, the new state is
| Face |
1 |
2 |
3 |
4 |
5
|
6 |
7 |
8 |
9 |
| 1 |
B |
Y |
Y |
B |
Y
|
Y |
B |
Y |
Y |
| 2 |
R |
R |
R |
R |
R
|
R |
R |
R |
R |
| 3 |
Y |
G |
G |
Y |
G
|
G |
Y |
G |
G |
| 4 |
O |
O |
O |
O |
O |
O |
O |
O |
O |
| 5 |
B |
B |
W |
B |
B |
W |
B |
B |
W |
| 6 |
G |
W |
W |
G |
W |
W |
G |
W |
W |
After applying the U operation from the initial state, the new state is
| Face |
1 |
2 |
3 |
4 |
5
|
6 |
7 |
8 |
9 |
| 1 |
Y |
Y |
Y |
Y |
Y
|
Y |
Y |
Y |
Y |
| 2 |
G |
G |
G |
R |
R
|
R |
R |
R |
R |
| 3 |
O |
O |
O |
G |
G
|
G |
G |
G |
G |
| 4 |
B |
B |
B |
O |
O |
O |
O |
O |
O |
| 5 |
R |
R |
R |
B |
B |
B |
B |
B |
B |
| 6 |
W |
W |
W |
W |
W |
W |
W |
W |
W |
State Representations
Each state is represented by a 54-character string using row-major. Therefore,
- The initial state is represented as YYYYYYYYYRRRRRRRRRGGGGGGGGGOOOOOOOOOBBBBBBBBBWWWWWWWWW
- After applying the F operation from the initial state, the new state is BYYBYYBYYRRRRRRRRRYGGYGGYGGOOOOOOOOOBBWBBWBBWGWWGWWGWW
- After applying the U operation from the initial state, the new state is YYYYYYYYYGGGRRRRRROOOGGGGGGBBBOOOOOORRRBBBBBBWWWWWWWWW
The centers always appear in the order YRGOBW. This is very important because we need a unique way to express each state.
Requirements
Your team needs to write a Java program (C++ not accepted) that takes one input as the name of the file containing commands. Your program prints the outputs of the commands.
The following are the commands.
- RESET:return the default state. At this state, all squares in each face has the same color.
- one of 18 possible operations: The 18 operations are
| X |
X' |
Y |
Y' |
Z |
Z' |
| F |
F' |
R |
R' |
U |
U' |
| B |
B' |
L |
L' |
D |
D' |
- OUTPUT: print the current state. It is a 54-character string followed by the new line ('\n') character.
- a 54-character string: set the cube to the state. This is always a valid state. Your program does not have to check whether this state is possible.
- comment: If a line starts with #, ignore this line.
Example of input files
RESET
X
F
R'
OUTPUT
RESET
F
X
U
L
B'
OUTPUT
RESET
U
D'
L'
F
B
OUTPUT
RRRYYGYYGWRRWRRBRRGGWGGWGGWOOYOOYOOGBBBBBBYYYWWBWWBOOO
Z
U'
R'
L
U
OUTPUT
This is a sample input and this is the corresponding output.
A (new) sample solution (binary) is avaiable.
The first stage of this project is completely text-based and it will be graded based on the output only. It is not necessary for your program to have a graphical user interface. You will need to construct a graphical user interface in Stage 2.
Grading (total 5 points)
- 1.2, (12 test cases) each of the 12 turn commands (without rotation) from the initial state
- 1.0, (10 test cases) sequences of up to 3 turn commands (without rotation) from the initial state
- 1.0, (10 test cases) one rotation command followed by up to 10 turn commands from the initial state
- 0.8 (8 test cases) a sequence of up 10 commands that may include multiple rotations and turns from the initial state
- 1.0 (10 test cases) a sequence of up 10 commands that may include multiple rotations and turns from a given state (that is not the initial state)
How is your program graded?
Your program must take one argument as the input file of commands. The program prints the results to screen. The grading program will redirect the output to a file and compares your results with the correct answers. In other words, this is how your program is graded:
[ terminal prompt ] your_program input > output
[ terminal prompt ] diff output expected_output
Nobody will interact with your program. Hence, do not print anything like, "Please enter a file name:".
References
Many web sites provide on-line Rubik's Cube games, for example
If you use anything (code, algorithm, formula, ...) that is not provided by this course (lectures, textbook, assignments, on-line discussion. office hours ...), you must cite the source of the materials. This class has zero tolerance of dishonest behavior.
|
