Table of Contents

1. Introduction
2. Mathematics
3. Representation
4. Representation Evalutation
5. Breadth-first Search
6. Iterative Deepening Depth-first Search
7. IDA*

1. Introduction

The Rubik’s Cube is a 3-dimensional puzzle invented by Erno Rubik in 1974. The traditional Rubik’s Cube has 6 faces, each with a different color. Typically, red is opposite orange, green is opposite blue, and white is opposite yellow. Each face has one center piece that may rotate in place, 4 edge pieces, and 4 corner pieces. Each edge piece is shared between 2 faces, and each corner piece is shared between 3 faces. The puzzle is designed such that each individual face may be rotated 90°, 180°, or 270° in either the clockwise or counterclockwise directions.

The puzzle is scrambled by performing a sequence of \(N\) rotations of any of the 6 faces. Each rotation will disrupt the permutation (position) and orientation of both the edges and corners. The center pieces are merely rotated in place, so we will not consider the state of those pieces as mutable. The cube is said to be solved when all colors on each of the 9 pieces of each of the 6 faces match. Our goal, then, is this:

Given a scrambled cube, produce the shortest sequence of rotations necessary to restore the cube to the solved state.

It is the word “shortest” in that description that will prove to be the most difficult part of this task. Finding a solution is relatively simple–finding the optimal solution is much harder.

With this series of posts, my goal is to demonstrate several methods for finding an optimal Rubik’s Cube solution, as well as their individual strengths and weaknesses.