A Rubik's cube is a 3 dimensional toy where the player can twist the surfaces to scramble the colored stickers on said surfaces. Rubik's Cubes come in many sub types. They can be made with any arbitrary number of layers. The classic cube is 3x3x3. I wrote a program for the 2x2x2 variant.
Given an arbitrary scrambled up cube, output the solution. The solution is a sequence of steps that when applied, restore the cube to the initial position, where all stickers on the faces are all the same color.
The app makes a breadth first search of permutations. It uses a OOP and a Set data structure to implement.
Essentially, these solvers are simple tree transversal programs. The space of permutations can be schemed as a tree with cubes created by more numerous amount of twists existing deeper in the tree than "simpler" permutations. For each permutation, which I will refer to as a "cube", there exists n more cubes one twist deeper in the tree. Well, provided that those twists actually get to a "deeper" permutation, and not back to another simpler one.
The question of solving the cube is a matter of calculating all possible cubes starting from solved, matching the scrambled state, and outputting the move list in reverse.
So some hurdles: How much RAM will this use? How does the app prune duplicate cubes so as not to recurse forever?
The solution was to store each cube in a data structure for comparison. At each twist generation the app compares to the existing data bank of cubes, and only adds to in if the cube is in fact newly discovered. Now that the data bank is free of duplicates it's a simple matter of iterating over all the deepest cubes until there are no more new cubes to discover. Or until RAM is exhausted. This is why I chose to write my app for a two layer cube. Classic three layer Rubik's cubes have way too many possible permutations.
So now that I've talked about general abstract principles of the app, I'll delve a bit into some specifics to demonstrate my computer science knowledge.
A cube is represented by an object using object oriented programming. The cube object has a 24 character array to represent the stickers. There is also a character array for the move list to generate that particular cube. And unfortunately, this is a shared character array. The move list starts on index 24, and is terminated with a special character. (0 is a possible move.) I made several constructors. The default constructor is to spawn a solved cube. That's useful for kicking off the app. The real workhorse is the constructor that takes in a cube, and a twist instruction, and creates a new cube.
A Rubik's cube of any size has six surfaces, and each of those can be twisted either 90 ° clockwise, 180 ° , or 90 ° counter clockwise. So that's a total of 18 possible moves. You can envision the tree of cube space as a 18 branch tree. But that's really only true for the initial solved cube. For each cube after that, twisting the same face two times in a row will merely take you to a cube on a neighboring branch. Or possibly back to where you came from, undoing the most recent twist. So my iterator skips the possible twists along the same face. But also in the case of a two layer cube, twisting opposite facing faces are logically equivalent. So I framed the design of the app to keep the orientation of the cube as a whole the same throughout, and limited the twists to only the right hand side. That's only 3 faces times 3 rotations, for a total of 9 possible moves. Since you don't want to repeat the same face, the tree really only looks like a 6 branch tree. Much less than the 15 for a three layer cube. Four layers and higher have "slice" moves resulting it even more possible moves available.
After creating the schema to generate and keep track of the cubes only the hard work of traversing the tree is left. I went with a breadth first search, since I wanted to find the best, shortest move solution. That was simple enough. (Once I figured it out). I dumped the cubes that passed a uniqueness test into a set. I made a list of sets, for each depth level so it was easy to count the number of cubes per depth level. When my counts were matching the expected numbers from the Wikipedia page I knew I was golden.
It has just come to my attention that a Hash Set might have better performance. Then the unique cube data bank could be searched in O(1) time. I'm not sure if std Set uses that or a binary tree. I might do some reading up in the future. But I don't feel like revisiting this project. It was a long time ago, and perfection is the enemy of good enough.
It's a good thing that I chose a small tree that fits entirely in RAM, but what if I wanted to tackle the three layer cube? Or four? Well I suppose the solution to that would be to do a mixture of depth first and breadth first searches. I could drop down deep enough such that a breadth first search would eat up all the RAM, and then run those sequentially making note of solutions. At the end pick the best solution. I believe that mirror transformations can be pruned as well. I'm also not entirely sure that my programming instructions to create the cubes were exactly close to the bare metal as possible. I wondered If "adding" cubes to the set after being validated was the fastest way to do it. Maybe there is some optimization to be had by building the cube directly in the set? It's all pointers though, so it probably doesn't matter right? But might it not be faster to just recreate cubes than to keep it on hand? Why not just keep move lists in a tree and recreate the cube as needed? Well I suppose it's because I suspect that looking it up in the binary tree of the set is faster. Thinking now I'm realizing how dumb I sound. Of course following a pointer is going to take less time that copying 24 characters around. Times depth. Duh.
It might be interesting to divide these math problems up into distributed computing systems. In my investigation I came across some interesting work on Sudoku puzzles. Apparently there are exactly 6,670,903,752,021,072,936,960 Sudoku solution grids. I hope that guy got paid well to prove it.