I have a passion for problem solving that almost parallels my desire to engineer software to solve those problems for me. Thus, today, I would like to talk about my efforts of learning how to solve a Rubik’s cube and engineering software to solve it for me.
Before I get into it, I would like to add a little disclaimer on my approach; I am aware that there probably are hundreds if not thousands of open source solutions ready and available. I’m not interested in those right now. What I want to do, before I ultimately arrive at the optimal, optimized solution is to tackle the problem myself.
So where would you start? Well, my initial instinct, although I have a fairly strong suspicion it wouldn’t work so well, is a brute force approach. Let’s run some experiments.
If we consider each clockwise and counter-clockwise, 90 degree rotation of a side as a unique move, the Rubik’s cube has 12 possible moves; 2 for each face. If we then take the known number of how many moves any cube can be solved with (20 or 26, depending on metrics), we can easily design a program that generates a list of all possible combinations of moves. If we then execute these movesets one by one against a cube, checking the state in between every execution, we can essentially brute force our way to the solution of any cube. How many possible movesets are we talking about though? Let’s do some math.
The number of movesets of length 20 that exist for a cube are:
Let’s expand that, just to get a better feel of the size of the number:
We can see that it’s larger than Java’s Long.MAX_VALUE, which is equal to:
Right, it’s pretty big. We’re probably going to have to do a bit of elimination when we generate that list of movesets. Nonetheless, computers these days do billions of operations a second with ease. Let’s run a rudimentary program to get a feel of how long it would take to iterate through all of those permutations.
Here’s what that program might look like:
Pattern quadMove = Pattern.compile("(\\w)\\1{3}");
String availableMoves = "abcdefghijkl";
List moves = new ArrayList();
long validMoveCount = 0l;
long invalidMoveCount = 0l;
for (int a = 0; a < 12; a++) {
for (int b = 0; b < 12; b++) {
for (int c = 0; c < 12; c++) {
for (int d = 0; d < 12; d++) {
for (int e = 0; e < 12; e++) {
for (int f = 0; f < 12; f++) {
for (int g = 0; g < 12; g++) {
for (int h = 0; h < 12; h++) {
for (int i = 0; i < 12; i++) {
for (int j = 0; j < 12; j++) {
for (int k = 0; k < 12; k++) {
for (int l = 0; l < 12; l++) {
for (int m = 0; m < 12; m++) {
for (int n = 0; n < 12; n++) {
for (int o = 0; o < 12; o++) {
for (int p = 0; p < 12; p++) {
for (int q = 0; q < 12; q++) {
for (int r = 0; r < 12; r++) {
for (int s = 0; s < 12; s++) {
for (int t = 0; t < 12; t++) {
String moveset = new String(String.valueOf(availableMoves.charAt(a))
+ String.valueOf(availableMoves.charAt(b))
+ String.valueOf(availableMoves.charAt(c))
+ String.valueOf(availableMoves.charAt(d))
+ String.valueOf(availableMoves.charAt(e))
+ String.valueOf(availableMoves.charAt(f))
+ String.valueOf(availableMoves.charAt(g))
+ String.valueOf(availableMoves.charAt(h))
+ String.valueOf(availableMoves.charAt(i))
+ String.valueOf(availableMoves.charAt(j))
+ String.valueOf(availableMoves.charAt(k))
+ String.valueOf(availableMoves.charAt(l))
+ String.valueOf(availableMoves.charAt(m))
+ String.valueOf(availableMoves.charAt(n))
+ String.valueOf(availableMoves.charAt(o))
+ String.valueOf(availableMoves.charAt(p))
+ String.valueOf(availableMoves.charAt(q))
+ String.valueOf(availableMoves.charAt(r))
+ String.valueOf(availableMoves.charAt(s))
+ String.valueOf(availableMoves.charAt(t)));
Matcher matcher = quadMove.matcher(moveset);
if (!matcher.find()) {
moves.add(moveset);
validMoveCount++;
} else {
invalidMoveCount++;
}
System.out.println("validMoveCount: " + String.format("%,d", validMoveCount)
.replaceAll(",", " ") + ", invalidMovecount: "
+ String.format("%,d", invalidMoveCount.replaceAll(",", " "));
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}First things first, the code uses the letters a through l to represent the 12 available moves. It also has a regular expression that takes a permutation and detects four identical consecutive letters:
Pattern quadMove = Pattern.compile("(\\w)\\1{3}");The moveset is tested against this pattern using the Matcher class:
Matcher matcher = quadMove.matcher(moveset);
if (!matcher.find()) {
...
}matcher.find() evaluates to true if the moveset the matcher was initialized with matches the pattern.
All of the movesets that match this expression can be considered invalid, as four identical consecutive moves to a cube does nothing; it just brings it back to the state it was in before the moves were made. There are more ways we can check movesets, but for simplicity’s sake, we’re only considering this pattern.
Running the above code for a few minutes makes a couple of things evident. One: a huge chunk of movesets are invalid. Two: this is going to take a really, really long time. But just how long are we talking? Hours? Days? On my system, which is pretty new, I see that the program powers through about a million movesets in 10 seconds, or 100 000 movesets per second. Since we know how many permutations there are to work through, we can calculate how long all permutations would take to evaluate in seconds:
In minutes, that’s the equivalent of:
Hours:
Days:
Years:
For reference, the current age of the universe is approximately:
So yeah, something tells me even an optimized brute force approach isn’t the way to proceed here.
What is the way to proceed though? As I mentioned in the beginning of this post, I have a bit of experience solving the cube by hand. Perhaps a human approach can help us engineer a solution. Stay tuned for more.