Description: The Rubik's Cube is a 3-D mechanical puzzle invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik. Originally called the "Magic Cube",
It is widely considered to be the world's best-selling toy.

Each of the six faces is covered by 9 stickers, among six solid colors (traditionally white, red, blue, orange, green, and yellow). A pivot mechanism enables each face to turn independently, thus mixing up the colors. For the puzzle to be solved, each face must be a solid color, this is a Perfect cube.



external image 480px-Rubik%27s_cube.svg.png
Algorithmic problem:
Input - A perfect cube(C) that has been mixed N times (each "mix" is a random turn).
Output - minimal list of turns that by following those turn one will get a Perfect cube.

Algorithmic Solution:
The best known algorithm is Iterative Depending A* using heuristics.

Heuristics:
1) 3D Manhattan distance - Unfortunately, to be
admissible, this value has to be divided by eight, since every twist moves four corner and four edge cubies

2) A better heuristic is to take the maximum of the sum of the 3D Manhattan distances of the corner cubies, and the edge cube, each divided by four.
The expected value of the Manhattan distance of the edge cubeis 5.5, while the expected value of the Manhattan distance of the corner cubeis only about 3, partly because there are 12 edge cubies, but only 8 corner cube.

3) Using heuristic #2 solving problem instances at depth 18 would take over 250 years.
In order to improve that one can use the pattern database
in the database we can save the heuristic function results in order to reuse it instead of recalculating it over and over again.
During the IDA* search, as each state is generated, a unique index into the heuristic table is computed, followed by a reference to the table.
The stored value is the number of moves needed to solve the corner cubies, and thus a lower bound on the number of moves needed to solve the entire puzzle.
We can improve this heuristic by considering the edge cube as well.

Reference:Finding Optimal Solutions to Rubik's Cube Using Pattern Databases by Richard E. Korf