The Challenge
I was playing with my son’s Rubik’s Cubes and tried to scramble a cube randomly so that no two squares with the same color were side by side. Here’s one way to do it:
But I wanted a scramble that looked like a random scramble. No matter how many different moves I made, I couldn’t do it. Every time I separated two squares with the same color, two other squares of the same color would touch somewhere else.
Looking for an easy answer, I went to puzzling.stackexchange.com and found this question:
The most impressive answer was by Florian F:
However, it’s clear that every face of this scramble has the same pattern:
A D A
B E B
C F C
I set out to try to find a better scramble.
The Requirements
Florian F introduced several requirements:
1) Every color on every face.
2) No more than two of any color on a face.
3) No two squares of the same color touching side-by-side on any face.
4) No two squares of the same color touching on a corner (or diagonally) on any face.
5) No two squares of the same color touching on a corner where two faces meet.
To this list, I added one more requirement:
6) Every face must have a different pattern.
This illustration shows a scramble that fails each requirement:
1) This face is missing yellow.
2) This face has more than 2 green squares.
3) Here are two yellow squares touching on a side.
4) Here are two blue squares touching diagonally.
5) Here are two green squares touching diagonally across two faces.
6) These two faces have the same pattern.
The Method
There are 43,252,003,274,489,856,000 ways to arrange a Rubik’s cube. If I could evaluate a million arrangements per second, it would take over 1.3 million years to evaluate all arrangements. So, inspecting every individual arrangement is out.
I looked for a way to programmatically assemble a cube that met the criteria. To know how to generate only cubes that are solvable, I had to learn how to evaluate a randomly-assembled cube to tell if it was solvable. I found this question on puzzling.stackexchange:
This provided a partial answer from which I was able to work out a full answer. There are 3 limitations:
1) I can place the first 7 corner pieces onto the cube any way I want. The orientation of the last corner piece is determined by the orientations of the first 7.
2) I can place the first 11 edge pieces onto the cube any way I want. The orientation of the last edge piece is determined by the orientation of the first 11.
3) I need to track how many swaps I create by placing those pieces. An even number of swaps is solvable, and odd number is not.
I decided to try to break the problem up by creating two candidate lists:
• A list of all corner piece arrangements that could be part of a perfect scramble
• A list of all edge piece arrangements that could be part of a perfect scramble.
I planned to pair up these lists to create a full scramble.
I didn’t know if the perfect scramble was possible, but Florian F’s solution showed that it is possible to meet requirements 1 – 4. I set that as the minimum bar and had the program save all solutions that met those requirements, separating the results by how much they met requirements 5 and 6.
Corners
For corner pieces, the only requirements I had to worry about were 2 (no more than two of any color on a face) and 4 (no squares of the same color touching diagonally). I treated the corner placement as a tree traversal. The top node is a skeleton of a Rubik’s Cube with just the center pieces filled in. This diagram shows a simplified version of the tree traversal.:
On second level, placing a corner piece with a white surface touching the white center is not allowed. Therefore, that branch stops there – there is no need to visit the 3,674,160 arrangements branching off of this node.
At the fourth level, placing three corners of the same color on a single face violates requirement 2. That branch is also pruned.
This is a very simplified view. I considered the entire cube, not just the one face shown. Also, the full tree has 24 branches from the first node (eight corner pieces to place in the first position, each with three different orientations), and 10 of them are dead ends at the first level. So 40% of the work is cut out at the first level.
Finally, I need to consider swap parity. A corner arrangement produced by performing an odd number of swaps must be combined with an edge arrangement that also uses an odd number of swaps, so that the total number of swaps is even. I split the corner arrangements into two lists, odd swap parity and even swap parity, intending to compare only odd swap parity edge arrangements to odd swap parity corner arrangements (and the same for even parity arrangements).
In the end, 88,179,840 possible corner piece arrangements were reduced to 750,640 candidates in less than one second!
Edges
The edge arrangements took significantly longer – there are nearly a trillion to arrangements to consider. Again, I could only consider requirements 2 and 4. To evaluate the other requirements, I need both corners and edges placed on a cube.
I had initially planned to build a list of edge combinations and then try each edge combination against each corner combination. However, the math showed that I would have had to perform trillions or quadrillions of comparisons, so I had to come up with something faster. I decided to compare each node on the tree with the list of corner arrangements and pruned a branch if there were no corner arrangements compatible with the edge arrangements. Thus, the comparison of edge and corner arrangements was done inline with the edge arrangement tree traversal. I had to go back and sort and index the corner arrangements so I could quickly jump from one compatible arrangement to the next.
The Solution!
In the end, the program took 5 days to run. Here is the solution the program found:
This meets all the criteria and … this is the cool part … it’s the only solution!
Now, you can hold the Rubik’s cube in one of 24 different positions and you can apply this solution or apply its mirror image, so there are 48 unique arrangements produced by this solution.
Here are the moves to produce the Perfect Scramble (Thanks to Redditor plutrichor for finding this optimal pattern and pointing me to Cube Explorer) :
Creating the perfect scramble: U F' L' U' R2 F' R2 B' U' R F' U F D' L2 F2 L2 U'
Solving the perfect scramble: U L2 F2 L2 D F' U' F R' U B R2 F R2 U L F U'
Creating the mirror image: U' F R U L2 F L2 B U L' F U' F' D R2 F2 R2 U
Solving the mirror image: U' R2 F2 R2 D' F U F' L U' B' L2 F' L2 U' R' F' U
Here are all 48 unique arrangements produced by the perfect scramble:
Could the program be faster?
Absolutely.
First, I could have made it multi-threaded. Since multi-threading only provides a linear speedup, I first optimized my tree searching, looking for better-than-linear speedups wherever I could. I planned to throw in multi-threading afterward, but once I saw that the program would finish in a reasonable amount of time, laziness kicked in and I just waited for the answer.
Second, knowing now that the perfect scramble is possible, I could prune any branches that violate requirements 5 and 6. Perhaps I could have started by performing that more restricted search first and then relaxing the requirements if it failed.
Can we add more requirements?
Since there is only one solution, any new requirements are either already met or impossible to meet, unless we remove one of the existing requirements.
For example, you could argue that a perfectly scrambled cube must take 20 moves to solve. My perfect scramble only takes 18 moves. To find a different scramble that takes 20 moves, one of the existing requirements must be relaxed.
After my program finished running, I thought of the requirement that no piece is in its original position. The perfect scramble fails to meet that requirement because it has one corner piece and two edge pieces in their original positions (which I use as landmarks to tell how to orient the cube when I solve the perfect scramble). To find a scramble that meets this requirement, one of the existing requirements must be relaxed.
On stack exchange, Florian F had one more requirement: All combinations of 4 colors meet at a junction of 4 corners. I ignored this requirement in my program, but it turns out that all combinations except one are present on a face. That combination, green-blue-orange-white, is present only on the edge of the cube. Thanks to Florian F for pointing that out! Again, this is as good as we can do, unless we relax one of the other requirements.
So there it is! Out of 43 quintillion possible arrangements, there is only one solution and 48 unique arrangements that satisfy the requirements for a perfect scramble. If you were to try to find this by trial and error, you would have to try an average of 900 quadrillion arrangements before you found one of these 48.
The Program
The source code for my program can be found here: https://github.com/telemath/PerfectScramble