For this assignment you will study and implement Korf’s algorithm for finding optimal solutions to random instances of Rubik’s Cube. Included with the assignment is a copy of Korf’s original paper. You should begin by reading the paper. Korf initially suggest using an iterative deepening version of A* (IDA*) with the heuristic. However, he points out that the inaccuracy of this heuristic results in too many nodes generated and therefore too much time to compute a solution. His answer to this problem is to precompute the heuristic for three components of the cube (corners, sides, sides) and store the values in a table. If these tables are small enough to be kept in memory, they can be referenced as part of the heuristic function. The assignment then breaks down into two steps:
1. Precompute the three tables for Korf’s heuristic and store the tables in a file. Be sure to choose a representation that is memory-efficient.
2. Write a program that takes an arbitrary cube state as input and outputs an optimal solution move sequence. Your program should read in the tables that you precomputed, and use IDA* and Korf’s heuristic to find the solution.
I/O
For both input and output we will use the letters {R, O, Y, G, B, W} to represent the colors {Red, Orange, Yellow, Green, Blue, White}, respectively.
Input
For input your program should take the name of a file that will contain an arbitrary cube state. The file will contain a specific two dimensional representation of the cube, using the letters above to describe each cube face. The structure of the two dimensional representation will be as follows:
Sample Files
The goal state would be: A valid non-goal state would be:
RRR GGW
RRR RRG
RRR RRG
GGGYYYBBB OWWGGOYYR
GGGYYYBBB OGOYYYRBR
GGGYYYBBB YYYRBGRWW
OOO BOY
OOO BOB
OOO BOB
WWW OGO
WWW WWB
WWW WWB
All spaces should be ignored when reading the files. Note that the six center faces are always the same in any valid state.
Invalid States
Not all arrangements of the faces are reachable from the goal state. The first thing your program should do is check that the input state is valid. If not, the program should output a message indicating that the state is invalid and terminate.
Output
Your program should output the optimal solution sequence for the input state as a string to standard input. The format of the solution sequence will be a string with two characters per move. The first character will be the color of the center cubie of the face to be rotated. The second character will be the number of 90° clockwise rotations, i.e. ∈ {1, 2, 3}. E.g., for the above non-goal state, the optimal solution would be O1W1R1Y3.
Language
You may use a programming language of your choice for this assignment. You are responsible for choosing a programming language and making it work. If you plan to use a non-standard language, be sure to start early so you have time to change languages if your approach does not work.
Report
In addition to the source code, report must contains the following:
• Explanation of your approach for computing and storing the tables
• Details about the tables, including number of entries and memory requirements
• Instructions for running your program
• Solutions for the ten sample states (to be provided)