Trying to implement a rubiks cube solver in C++
My goal for this project is to first implement and benchmark different solving algorithms, and later, create a fully autonomous robot that can solve any scrambled 3x3 cube. See more about this at the end. I am currently in the model and alorithm implementation stage.
When I was 12, I got a Rubik's cube for Christmas and I spent the entire rest of the day figuring out how to solve it. This was the beginning of my interest in cube puzzles and over the next few years I spent countless hours playing with them. I was able to solve 2x2, 3x3, 4x4, 5x5, and 7x7 puzzles, as well as some weird ones like a megaminx. At my fastest, I was able to solve a 3x3 in 15-20 seconds.
Ever since I became interested in coding, I have always wanted to implement an algorithm to solve an arbitrary scramble state of a Rubik's Cube. This past year I finally felt ready to tackle this challenge, so I grabbed my cube and my laptop and started to research.
The first step was to pick a programming language and figuring out the best way to represent the cube in code. I decided to use C++ for its speed and versatility. I created a cube class that defined several uint8_t enums for representing the faces, slices, colors, edges, corners, and moves. I also made methods to get the color of a piece, apply any rotation or move to the cube, and check if the cube is solved.
I started by using two arrays to store pieces and centers. The indices cooresponding to the real cube are stored in the pieces array starting with the upper back left, and finishing at the lower back left, like so:
std::array pieces;
std::array centers;
0 1 2 32 33 34
7 3 39 35
6 5 4 38 37 36
8 9 10 16 17 18 24 25 26
15 11 23 19 31 27
14 13 12 22 21 20 30 29 28
40 41 42
47 43
46 45 44
This is the get_color() method that takes an index.
COLOR get_color(unsigned index) {
return (COLOR)this->pieces[index];
}
The key with this representation is that because each COLOR is a single byte, we can represent an entire face (not including the center) with 8 bytes in a uint64_t.
This allows a very simple check to see if the cube is solved. Check every face against its initial value and if all of them match, then the cube is solved. The method looks like this,
bool is_solved() {
return
this->get_face(FACE::up) == 0x0000000000000000 &&
this->get_face(FACE::left) == 0x0101010101010101 &&
this->get_face(FACE::front) == 0x0202020202020202 &&
this->get_face(FACE::right) == 0x0303030303030303 &&
this->get_face(FACE::back) == 0x0404040404040404 &&
this->get_face(FACE::down) == 0x0505050505050505;
}
The get_face() method that is being used here might be a little confusing at first but it helps illustrate the value of representing each face with a single 64 bit number.
uint64_t get_face(FACE f) {
return (uint64_t*)&this->pieces[(unsigned)f
8];
}
What this is doing is finding the index of the first piece of the given face in the pieces array by doing FACE * 8. The memory address of this index is then cast to a uint64_t pointer and finally dereferenced, to get the 8 byte representation of the face.
Another convenience method that will be needed for the solving algorithm is get_color(), which is an overloaded method that either takes a face, row, and column or just an index as parameters.
COLOR get_color(FACE f, unsigned row, unsigned col) {
if (row == 1 && col == 1) {
return (COLOR)this>centers[(unsigned)f];
}
else {
unsigned lookup[] = {0, 1, 2, 7, 0, 3, 6, 5, 4};
unsigned index = lookup[row * 3 + col];
return (COLOR)this->pieces[(unsigned)f * 8 + index];
}
}
Next, I started to work on the moves. The move notation is simple, with u representing a 90 degree clockwise turn of the Up face and u' representing a counter-clockwise turn. 180 degree rotations are represented as u2. Each face differs only in the letter used, f for front, b for back, l for left, and so on.
The methods to make the moves are pretty repetitive and involve switching around values within the pieces array. There are a couple tricks I used to but I haven't benchmarked the performance differences yet.
There are several convenience functions used for making moves like rolling all pieces in a face. To do this, I extracted the 8 byte representation of the face, and ran a 'rolq' instruction on that. Then simply replace the value. This is what that looks like,
void roll90(FACE f) {
uint64_t face = (uint64_t*)&this->pieces[(unsigned)f
8];
asm volatile ("rolq $16, %[face]" : [face] "+r" (face) : );
(uint64_t*)&this->pieces[(unsigned)f
8] = face;
}
And this is what a couple of the methods look like. Several of them, including this one, use bit manipulation to quickly swap colors around the array.
Cube& u() {
this->roll90(FACE::UP);
uint32_t start_mask = 0x00ffffff;
uint32_t end_mask = 0xff000000;
uint32_t left = (uint32_t*)&this->pieces[(unsigned)FACE::left
8];
uint32_t front = (uint32_t*)&this->pieces[(unsigned)FACE::front
8];
uint32_t right = (uint32_t*)&this->pieces[(unsigned)FACE::right
8];
uint32_t back = (uint32_t*)&this->pieces[(unsigned)FACE::back
8];
(uint32_t*)&this->pieces[(unsigned)FACE::left
8] = (front & start_mask) | (left & end_mask);
(uint32_t*)&this->pieces[(unsigned)FACE::front
8] = (right & start_mask) | (front & end_mask);
(uint32_t*)&this->pieces[(unsigned)FACE::right
8] = (back & start_mask) | (right & end_mask);
(uint32_t*)&this->pieces[(unsigned)FACE::back
8] = (left & start_mask) | (back & end_mask);
return *this;
}
After creating the cube object and all the needed functionality, I could start to explore the actual solving algorithm. I found that there were several options for this, each with their own strengths and weaknesses but I ended up learning about 3 in particular.
The first algorithm is the Thistlewaite algorithm. It is based on grouping and dividing the problem into smaller subproblems.
Next was Kociemba's algorithm, an improvement to Thistlewaite. It uses the same grouping idea but with fewer groups and using a lookup table to help with remembering a large number of states.
The final algorithm is Korf's algorithm. The first two can solve a cube relatively quickly in a smallish number of moves (<100) but this is used for finding optimal solutions so it takes a lot more processing. The solution is built using an IDA* algorithm that uses large pattern databases to efficiently search potential states.