(Scroll down to play with the cube!)
Welcome! This is perhaps the flashiest project I completed during my time in school: an interactive Rubik’s cube with the ability to solve itself. I will be cleaning up the code and publishing it soon, but for now, I’d like to highlight some key concepts and points of interest.
This project started as a very ambitious endeavor for my AI class. I had initially intended to design a system which would develop cube solutions gradually through some kind of learning algorithm. Of course, I realized quickly that this was a fool’s errand. Teaching a computer to measure its progress towards a solution, a fundamental need of a learning algorithm, was a much more difficult task than I should have expected to complete in an introductory AI course. I settled on a rules-based approach, which I expected to be much more achievable.
Of course, generally describing how to solve the cube isn’t so hard when the listener has some intuition of his/her own, but a computer must be taught everything. I had to figure out how to represent the status of the cube in a way that was useful to the program. I had to describe movement of this representation. Finally, I had to figure out how to turn my own home-grown strategies for how to solve the cube into C#. This last part was both the most challenging and least interesting.
To start, the cube is represented in memory via a 2-dimensional array of 12×9 integers. Each little face of the cube has a unique number associated with it. The numbers are unique because each “piece” of the cube grid is a unique set of squares, unlike any other in the rest of the cube. They are more than simply red or white or yellow, they are “red and yellow” or “red and white and green.” That made everything a little easier because there is only one true home for every single face. If I store a copy of the un-moved cube at startup, the program has an example of what its goal is!
When making movements on this array, my first thought was to try some bizarre modular math to shuffle all the numbers manually. When this proved infeasible, I sought out other options. Luckily, I wasn’t the first to try and create a purely logical model of a Rubik’s cube. It turns out, the cube is an excellent and popular introduction to permutation groups! Put simply, a permutation group is an ordered array of numbers that describe a transformation on another set of numbers. Put less simply, here’s an example of my permutations:
Permutations.Add(new int[] {1, 3, 8, 6});
Permutations.Add(new int[] {2, 5, 7, 4});
Permutations.Add(new int[] {9, 33, 25, 17});
Permutations.Add(new int[] {10, 34, 26, 18});
Permutations.Add(new int[] {11, 35, 27, 19});
This set of arrays describes the shifts in the cube array whenever one turns the white face. Following along, we see that the number in position 1 goes to position 3, the number in position 3 goes to position 8, the number in position 8 goes to position 6, and the number in position 6 goes to position 1. So on and so forth. It’s tedious to do by hand, but an excellent, ambiguity-free model for a computer to follow!
Finally, the solving. I decided to implement the algorithm that I learned as I was attempting to solve the cube on my own. It’s very similar to the typical algorithm taught on the Rubik’s cube website and uses all the same stages, but I had to get creative with some of the later steps (and in this case, creative pretty much means inefficient!) This was something of a brute-force endeavor, and I didn’t have much time to develop more elegant solutions in school, but it got the job done. The code does not consider efficiency, merely looking for the next piece that’s out of place in a pre-programmed sequence. For example, the code might place the white-green piece, the white-red piece, the white-blue piece, and the white-orange piece in order every time, regardless of whether that was the most efficient sequence. The benefit of this strategy is that it is very predictable, so the many hang-ups that the code ran into ended up being reproducible. The main drawback for the user is that it may not be as fun to watch the program take 50 extra moves to get to the solution!
That’s all I have for now. I hope to continue work on this in the future, after I work out some more technically-complicated projects. Someday you’ll get to see all the cruft under the hood, and you’ll truly understand what a madman I had to be to see this project through! As always, if you have any questions, feel free to email me at me@andrewdys.art and I’ll be happy to answer!