Solving Rubik's Cubes with Computers
The first place I got into programming was making games. You can probably dig up some games I made long ago if you try hard enough (do not).
In high school, my focus on programming went over to implementing solvers for various Rubik's Cube like puzzles.
Since this is the first thing people wonder when I mention stuff like this, I was okay (this was like ~80th worldwide at the time, although nowadays it wouldn't be worth mentioning):
Anyway. I got very into implementing solvers for various puzzles. There was a dearth of usable, graphical solvers for even mildly obscure puzzles at the time (I think nowadays there's probably a lot of them out there, though I couldn't say). This was how I learned about search algorithms.
The canonical resource for how to implement solvers was, and to the best of my limited knowledge, still is Jaap's Puzzle Page, specifically the page Computer Puzzling. I learned all of this from Jaap!
Now this is a historical artifact. I pored over this page as a young'un. There's so much good stuff here. But from the NULL BITMAP perspective, let's just take a...now hang on (emphasis mine):
God's algorithm is the name for the method of solving a puzzle which always uses the fewest possible moves. There are a few puzzles for which this already completely known (e.g. Pyraminx, 2×2×2 cube, Skewb), but many puzzles have just too many possible positions to be able to calculate God's Algorithm for all possible positions. As the cost of memory and processing power comes down more and more, puzzles that were previously out of reach become possible. Yet there are many puzzles which have such astronomical numbers of positions that it is hard to imagine that they will ever be fully solved.
For any position, God's algorithm can give a move that brings the puzzle one step closer to being solved. It is essentially just a large database, in which a position can be looked up, and from which you can extract the move to perform. To fully solve a position, just keep looking up the current position and doing the move the database tells you to, and eventually the puzzle will be solved. To find God's algorithm you therefore have to generate such a database only once, after which it can be reused forever.
Wait a second, that's me! That's us! We love the D word over here.
Okay, so, Jaap is clearly using the word "database" here in not quite the same way that we use it. But no matter, we can talk about some of the fun aspects of computer puzzling.
The Rubik's cube is comprised of 20 moving pieces: 12 edges and 8 corners. It also has six "centers" but since those never move in relation to each other we usually just think of those as anchoring the orientation that you hold the cube at.
Fundamentally, you can think of a cube, or any puzzle of this type, really, as a sort of state machine: there are six inputs:
- U: turn the top face clockwise
- D: turn the bottom face clockwise
- L: turn the left face clockwise
- R: turn the right face clockwise
- F: turn the front face clockwise
- B: turn the back face clockwise
Plus we usually consider multiple applications of those moves (technically you only need 5 of them, but it's easier to just say it's the 6).
The problem of a solver is to input the current state of the cube and then output a sequence of moves that brings it to the solved state. Of course, this is a simple graph-traversal problem.
The problem is that this graph is hella big. The number of states on a 3x3 Rubik's cube is
(we'll get into the derivation of this computation later.)
That is very big. We can't just search it. There's lot of fun techniques involved in this, but today I want to focus on just one small piece of it that I think is cool.
The "database" that Jaap talks about above is really "tables," lots and lots of lookup tables that tell you things about the various components of a Rubik's Cube.
As we said, a Rubik's cube has twenty moving pieces, 12 edges and 8 corners. Each of those moving pieces has two pieces of information attached to it:
- the way it's flipped in its current location, its orientation, and
- the position on the cube it's located in, its permutation.
The state of the cube is the product of these four states:
- edge orientation (EO),
- edge permutation (EP),
- corner orientation (CO),
- corner permutation (CP).
This is how we can arrive at our computation of the number of states on a cube:
- each edge can be flipped one of two ways, giving it size 2^12,
- there are 12! ways to arrange the edges, giving it size 12!,
- each corner can be rotated one of three ways, giving it size 3^8, and
- there are 8! ways to arrange the corners, giving it size 8!.
But... not really, since as you saw, we do some division. Don't worry about that. Unless you know some group theory. Then think about it. The important thing is that once you know the orientation of the first 11 edges, you can always determine what the orientation of the last one is, and similarly for the corners, and the permutations of the edges and corners are entwined in a way that is very interesting but not what I want to talk about today.
So, when you individually track each of these components of a cube, since they're pretty big, and lookup up states in a table is basically the hot loop of a cube solver, we would like that to be as fast as possible. Ideally, we want to map each of these states densely to an integer in [0, n), where n is the number of states. Also, for convenience sake, it's usually desirable if the solved state is 0.
For orientation, this is pretty easy: we can just look at the pieces that matter, that is, all of them minus one, and interpret the position as a base k number, where k=2 for edges and k=3 for corners:
fn main() {
println!("{:?}", index_orientation::<4, 3>([0, 0, 0, 0]));
println!("{:?}", index_orientation::<4, 3>([0, 0, 0, 1]));
println!("{:?}", index_orientation::<4, 3>([0, 0, 0, 2]));
println!("{:?}", index_orientation::<4, 3>([2, 2, 2, 2]));
}
fn index_orientation<const N: usize, const K: usize>(state: [u8; N]) -> usize {
let mut result = 0;
for i in 0..N {
result = result * K + state[i] as usize;
}
result
}
0
1
2
80
It's a little harder to think about how to do it for a permutation, though! Like, try it. It's a fun little challenge—not too hard if you're willing to put some time into it.
The answer is to use a completely different kind of numeric base, called factoriadic.
Recall a permutation for us is a sequence of the numbers [0,n) in some order. It's more common in math to label these [1,n] but since we're working with code I'm going to leave it 0-indexed. As an additional convenience, it's often desirable for the permutations to be labelled lexicographically, so we require that constraint as well.
[0,1,2,3] <- the solved permutation with four elements.
[0,1,3,2] <- the next permutation.
To do this, we give each place a value corresponding to the number of possible positions in the permutation that follows it. So the first one has a value of (n-1)!, the second one has a value of (n-2)!, and so on. The trick is that we have to account for the fact that the following, structurally smaller permutation might have numbers that are "too big" for it.
[1,3,2,0]
First, we look at 0, and say this position is worth (n-i-1)! *p\[i\] = 3! * 1 = 6, and add that to our sum.
Now we look at the next, recursive permutation:
[3,2,0]
However this is not a valid permutation! So we need to account for the fact that there is no more 1 and conceptually update the numbers in each position by decrementing the ones that come after 1:
[2,1,0]
And then we just recursively index this new permutation.
In code, this looks like this:
fn main() {
println!("{:?}", index_permutation::<4>([0, 1, 2, 3]));
println!("{:?}", index_permutation::<4>([0, 1, 3, 2]));
println!("{:?}", index_permutation::<4>([3, 2, 1, 0]));
}
fn index_permutation<const N: usize>(state: [u8; N]) -> usize {
// there are better solutions to this, but this is simple.
const FACTORIALS: [usize; 9] = [1, 1, 2, 6, 24, 120, 720, 5040, 40320];
let mut result = 0;
for i in 0..N {
let mut true_value = state[i] as usize;
// Check how many values came before this one that require us to decrement.
for j in 0..i {
if state[j] < state[i] {
true_value -= 1;
}
}
result += true_value * FACTORIALS[N - i - 1];
}
result
}
And that's how you index cube states! But actually, there is more subtlety to it than that. If I decide to talk on this topic again (and if people are interested) we can get into it more.