Rubik’s Cube Solver#
For AP Computer Science, I was required to complete a programming project of some kind. Because of my interest in Rubik’s Cubes, I decided to combine some of my passions and do something related to cubing for my project.
Simulator#
I first decided to write a Python program to simulate a Rubik’s Cube. A user would be able to enter moves on the command line and see a real-time display of the cube’s state. Here is an example of what this looked like in 2x2 mode:
Solver#
After successfully accomplishing this goal, I decided to build out a solver capability. This is where it really got fun, and I was able to apply some of my CS/algorithms skills.
Brute Force#
First, I tried making a brute force solution generator. It searched through every possible turn until a solution was found. However, this was extremely inefficient and could not feasibly be done, even in an entire lifetime. Read more on The Devil’s Algorithm to understand how truly difficult this is.
Parallel Version#
Since the regular brute force method didn’t work and I had recently finished an internship at INL HPC, I set out to implement a parallelized version of this technique with MPI. I did this, and ran the code on my Raspberry Pi cluster. However, the problem complexity simply overpowered my very limited resources.
State Inspection & Algorithm Selection#
Eventually, I realized that I make much better decisions than a brute force algorithm when solving a cube. I figured that a much more suitable approach would be to teach the computer what my method is, and let it generate solutions that way. I call this technique “state inspection and algorithm selection” since we strategically choose algorithms to get nearer to a solved state by inspecting the current state.
Ultimately, this was the fastest and most efficient method. I turned it in as my AP Computer Science project and received full points.