Overview
Once the color reduction issue is fixed, we have several other interesting problems still at hand.
- computing configurations of cubes : from images to finished cubes.
- implementing these configuration in real life on six hundred cubes : from defined computer known cubes configurations to physical world.
Computing cubes
Constraints on Rubik's cubes
The pixels displayed with facelets on each side of the cube can not adopt any combination.
Some constraints are imposed by the cubies themselves:
- the two center facelets have two colours from opposites sides of the cube
- no more than four corner facelets (out of height, four on each face) or four edge facelets can show the same colour
- there are more constraints, but they are more difficult to express. Let's assume white is opposite yellow ; if we consider only corner facelets, it is not valid to display four white pixels and three blue on the same cube, as there are four corner cubies with a blue facelet, but two of them are required to show white pixels... We may want to be more specific here, and get an exact expression of which combination are permited.
And there are also "parity" constraints imposed by the cube permutations: if one break a cube apart, using a screwdriver, and put it back together randomly, eleven time out of twelve, the cube will reach a state that can not be "solved". More specifically, if a cube is in a "valid" configuration:
- there is always an even number of edges that are flipped,
- the sum of elementary rotation on corner cubies is always a multiple of three,
- the total number of permutation of cubies (including both corners and edges) is even.
As we will have four hidden edge cubies, we can accomodate constraints 1 and 3 can be arranged with no difficulty. Obviously the second one remains an issue.
Strategy
The way we display the two images will have to workaround these constraints. The probleme may look similar to displaying images using characters, with a major difference : the alphabet here is probably too big to work with. How big exactly ? I'm still not 100% sure. -- K
So the strategy is:
- compute the best image possible, dealing only with color reduction
- install valid cubes behind the "required" pixels: putting one cubie after the other, with the "right" facelet displayed when possible. We know it won't be always possible...
- perform local improvements on the two pictures by applying randomly "valid" changes on the cubes, and keeping one if and if only it improve the picture.
Valid small impact moves
This "improvement" phase on the picture requires to changes the still virtual cubes. But rotating a face by 90° is probably not a good idea. But we can apply complex "algorithms" on the cube that have small impact:
- rotate two corners in opposite direction
- rotate three corners in the same direction
- rotate one visible edge and on hidden edge
- swap three corners, keeping the same facelet shown
- swap three edges
- swap two corners and two hidden edges
- swap two visible edges and two hidden one
- swap one visible edge and any hidden one
Some of these "moves" are redundant. All of them are "valid".
Implementing the cubes configurations
Once we know what configuration we want our cubes in, we need to implement this in the physical world. We own six hundreds cubes and have lots of friends.
Our cubes
We have 600 hundred cubes. Three of them are "grossly invalid" (yellow not facing white) and will have to be dealt with somehow. Then about half of them are mirrors images of the other half. We will have to "mirror" half of our virtual cubes to match this (but we know it can be done without impacting what is shown).
Back-solving the cubes
It is sensible to think that lots of people could learn how to solve the cube in a few minutes. For a computer, solving for the "solved" state or solving for a arbitrary state is the same. But the human solving method rely on visual clues to decide what to do next. The arbitrary target would make it very difficult to solve the cubes this way: the computer will have to do the thinking for us.
But applying a computer generated move to a cube is not that easy, so it is crucial that moves are kept short to avoid human error.
Automatic solvers are usualy tools that accept a cube configuration as input, check it is a valid cube, and more or less slowly propose a shorter or longer sequence that will restore the cube. As we are interested in the opposite process, we will have to inverse the move, but this is a no-brainer.
The solving methods
- layers-based methods: very fast and easy for human solving, in 50 to 150 face rotations depending on the number of memorized algorithms
- fewer algorith-small impact method: they generates more moves, easier to learn, less easy to apply. They are also used for blindfolded solving.
- (semi) optimal solving: more or less brute force method, only manageable by a computer. They will lead to 15 to 30 moves solutions.
Automatic solving
Michael Reid produced two solvers. One is the so-called "optimal solver" (I'm not 100% sure it is *realy* optimal). The other is the one behind Tom Davis Rubik program. Tom sent the original code to me.
The optimal solver takes between 60 and 120 minutes to crack a cube... The other is not significantly faster, as far as I can tell. We will need lots of CPU time, here.
Distributing the optimal solver
We are considering using a CPU share cluster. We may throw some EC2 instances in the bucket to boost the cube cracking process if we need to.
Avoiding mistakes
As it is very error-prone to blindly apply arbitrary moves sequences on a cube, we will want to provide as much visual help as we can.
