ECE 462 Fall 2010,

Group Programming Assignment

Stage 3 (C++ and Qt) Computer Solver

Summary

You need to develop an algorithm and write the code for solving the Cube. Your program may have the freedom using all 18 operations or only some of them.

Input

The program may receive one or two arguments. The first argument is the current state of the Cube. If the second argument is not provided, all 18 operations are allowed. If the second argument is provided, it specifies the allowed operations in a string surrounded by double quotes.

• example 1 (all 18 operations are allowed)

OYYBYYBYYBRRBRRBRRYGGYGGYRROOOOOOGGGBBWBBWOOWGWWGWWRWW

• example 2 (only FRUBLDXYZ are allowed; F' can be performed by FFF)

RRRYYGYYGWRRWRRBRRGGWGGWGGWOOYOOYOOGBBBBBBYYYWWBWWBOOO "FRUBLDXYZ"

• example 3 (only FF'RR'UBB'LDXY are allowed; neither Z nor Z' is allowed)

BYYBYYBOORRYRRYRRROGGOGGYYYWBBWOOOOORRWBBWBBWGGGGWWGWW "FF'RR'UBB'LDXY"

If the second argument is provided (i.e. some operations are disallowed), the allowed operations are sufficient for solving the cube. Your program does not need to check.

The arguments will be given through the command line, i.e. argv in main.

Output

The program's output is the sequence of operations to solve the Cube. The output must contain only the allowed operations. For example, if R' is not allowed, your program may use RRR to have the same effect as R'. Each line contains only one operation.

• example 1 (This is not necessarily the solution for the previous example)

F
B'
U
D

• example 2 (This is not necessarily the solution for the previous example)

X
L
Z'
R
D'

A better algorithm can solve the Cube using fewer commands. At this stage, your program needs to be correct and does not have to be efficient. At stage 4, your program will compete based on the number of commands.

Grading (5 points)

If your program uses more commands than necessary and the result is correct, you receive no penalty. For example, if one state can be solved by using F' and your program can use FFF, you will recieve the point.

• 1.2, (12 test cases) only one operation is needed to solve the cube. All 18 operations are allowed.
• 1.0, (5 test cases) up to 2 turn commands (without rotation) are needed to solve the cube. All 18 operations are allowed.
• 1.0, (5 test cases) up to 4 commands (rotations may be included) are needed to solve the cube. All 18 operations are allowed.
• 0.8 (4 test cases) up to 6 commands are needed to solve the cube. Rotations are disallowed.
• 1.0 (5 test cases) up to 6 commands are needed to solve the cube. Some commands are disallowed.

To make grading efficient, we will examine at most 90 commands. If your program cannot solve a cube within 90 commands, you will not receive the point. The correctness is determined by the cube's final state after executing all commands provided by your program.  Suppose

F
R
U

solves the cube and your program's output is

F
R
U
D

you will receive zero due to the additional command. 

For this stage, GUI is unnecessary but you may still want to create a GUI to help you visualize your solutions.

Timing Constraints

To ensure that your program produces a solution timely, your program can spend at most 30 seconds between two consecutive commands. Since only 90 commands are allowed, your program will not be graded if it fails to produce a solution within 90 x 30 = 2700 seconds, or 45 minutes.

Test Strategy

You can generate many test cases by using the solution for stage 1. Check whether your solution for stage 3 can find the reverse operations.