[Click here to download the Rubik’s Cube Solver]
I have never been able to solve a Rubik’s cube. I can get to the point where one side is correct before getting frustrated. But then I invariably try to get one more piece in place and end up ruining the whole thing. With that in mind, I decided to write a computer program that would solve a Rubik’s cube for me.
First, I wanted a way to display the cube and manipulate it. Displaying a 3D surface on a 2D computer screen is always a bit tricky because you can’t see the entire object. My initial thought was to show the “unwrapped” cube, where the six faces are joined at the appropriate edges. For rotation the user would be able to move any row or column on the front face in either direction. Because they could only manipulate the front face I added the capability to rotate the entire cube to show any of the adjoining faces.
This was a mess.
The “unwrapped” cube creates issues because no matter how you unwrap it one of the faces will be upside-down from what it should intuitively look like. Additionally, it’s restrictive to think about rotating the cube by only manipulating the front face. A quick search showed that there is actually a standard nomenclature for manipulating a Rubik’s cube. F denotes rotating the front (F) face of the cube 90 degrees clockwise. F’ is a counterclockwise rotation.
With this knowledge I modified my display to show each of the six faces independently, with buttons to rotate them clockwise or counterclockwise. I added similar buttons and icons to rotate the entire cube along any of its three axes. In the earlier version I had created a 3D rendering of the cube that displayed the front, up, and left faces. I added a see-through view of the cube next to this so that the back, right, and down faces of the cube would be visible in 3D as well.
Once I had written the code to rotate the faces and cube appropriately I added two buttons. The first to reset the cube to a solved state - the equivalent of peeling the stickers off and putting them back in the right place. The second to randomly perform some number of rotations along different faces and axes until the cube was nicely randomized, but still guaranteed to be solvable. Finally, it was time to add a button to solve the cube.
There are a variety of ways to solve a Rubik’s cube and this is by no means the most efficient. I wanted to follow a structure that led itself to programming and could potentially teach a person how to solve the cube themselves. The process treats the cube as having three layers, like a cake. It starts by solving the top layer, then the middle, then the bottom.
A cross of a single color is formed first on the top layer, and then the corner pieces are put into place. It is important that not only are the colors on the top correct, but the edges as well. Having done this there are only four spots in the middle layer that might need adjusting and only four spots that they could potentially be. To solve the bottom layer the program actually flips the cube over and then solves the upper layer again. However, it uses a more complicated set of rotations to ensure that it doesn’t change anything in the other, completed layers.
With the solver algorithm developed I decided to add a second worksheet that would list the steps so the user could follow along. The idea is a user could color the squares to match a real cube and then run the solver to discover what steps to take in order to solve it. They could then follow each step, rotating their own cube, and see how it is solved. If nothing else, at the end of the process they would have a completed cube to impress and amaze their friends.
Because my solver algorithm follows this layer concept it is by no means the most efficient way of completing a cube. Running it on randomly scrambled cubes I’ve found that it generally takes between 200 and 250 steps to solve it this way. At some point in the future I might look at optimizing my solver to use fewer steps I’m fairly happy right now that the thing actually works. Enjoy!