Originally taken from Breck Fresen’s page
Here’s a quick video of the program in action:
Download the source here. To compile for Win32, you’ll need to link in the OpenGL DLL’s.
Background
At the end of freshman year my friend Breck and I teamed up to write an optimal Rubiks Cube Solver that runs in a reasonable amount of time (not days like Richard Korf). The program randomly scrambles the cube and then solves it in the fewest number of turns possible.
Rubik’s Cube presents an interesting search problem because the cube space is so large – 43 quintillion combinations – that even if we could compress our cube representation to the theoretical minimum of 66 bits, we would only be able to store 1 one-hundred-billionth of all possible cube states in RAM at any given time on a 32 bit machine.
Implementation Discussion
With lessons learned from Path Finder, we started simple. Initially we scrambled the cube with just a few turns and used breadth-first search to solve it. On his laptop (1GB of RAM), this could solve cubes scrambled to a depth of 5 turns before the program started paging.
Next we implemented a double-ended breadth first search (where the scrambled cube searches for the solved cube and the solved cube searches for the scrambled cube). Double-ended searches (aka two frontier searches) are more efficient than their one-way counterparts on graphs with any significant branching factors because 2 * O(n) is much smaller than O(2 ^ n). This allowed us to solve cubes that required 10 turns, and we could do it in 2 minutes or less.
Our cube representation also improved. Initially we represented each face by a 3×3 array of 32 bit ints, which wasted a significant amount of space. Ultimately we settled on bit fields, where each cube face was represented by 9, 3 bit numbers (where each 3 bit number represented one of the 6 possible colors). This reduced our cube size from 216 bytes to 24 bytes.
Finally we implemented double ended A*, which required our first bit of serious thinking. Picking a heuristic for the cube space that always underestimates the distance to the goal (a requirement for A* to return an optimal path) was non-trivial. Ultimately we realized that a single turn can correct at most 4 edge-corner pairs and 4 edge-center pairs. This turned out to be an excellent heuristic. It got us another depth out of each end of the A* search, meaning the laptop could solve cubes scrambled to a depth of 12 or less without paging, which is where the program stands now.
I believe it’s been proven that there exists a cube – the superflip – which requires at least 24 quarter turns to solve. So we’re still a long way from being able to solve every cube optimally. But this program is an excellent example of how progress happens when you attempt a problem you’re not entirely sure you can solve. Try, test, improve. Iterate.