---
tags: hpc, algorithms, development
date: 2018-03-20
---

# 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:

```{image} /_static/images/cube-solver-simulation.png
```

## 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](http://anttila.ca/michael/devilsalgorithm/) 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.