| 26 | == Strategy == |
| 27 | |
| 28 | 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'' |
| 29 | |
| 30 | So the strategy is: |
| 31 | 1. compute the best image possible, dealing only with color reduction |
| 32 | 2. 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... |
| 33 | 3. 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. |
| 34 | |
| 35 | === Valid small impact moves === |
| 36 | |
| 37 | 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: |
| 38 | * rotate two corners in opposite direction |
| 39 | * rotate three corners in the same direction |
| 40 | * rotate one visible edge and on hidden edge |
| 41 | * swap three corners, keeping the same facelet shown |
| 42 | * swap three edges |
| 43 | * swap two corners and two hidden edges |
| 44 | * swap two visible edges and two hidden one |
| 45 | * swap one visible edge and any hidden one |
| 46 | |
| 47 | Some of these "moves" are redundant. All of them are "valid". |
| 48 | |
| 51 | 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. |
| 52 | |
| 53 | == Back-solving the cubes == |
| 54 | |
| 55 | 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. |
| 56 | |
| 57 | 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. |
| 58 | |
| 59 | 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. |
| 60 | As we are interested in the opposite process, we will have to inverse the move, but this is a no-brainer. |
| 61 | |
| 62 | The solving methods |
| 63 | * layers-based methods: very fast and easy for human solving, in 50 to 150 face rotations depending on the number of memorized algorithms |
| 64 | * fewer algorith-small impact method: they generates more moves, easier to learn, less easy to apply. They are also used for blindfolded solving. |
| 65 | * (semi) optimal solving: more or less brute force method, only manageable by a computer. They will lead to 15 to 30 moves solutions. |
| 66 | |
| 67 | == Automatic solving == |
| 68 | |
| 69 | Michael Reid produced two solvers. [http://www.math.ucf.edu/~reid/Rubik/optimal_solver.html 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. |
| 70 | |
| 71 | 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. |
| 72 | |
| 73 | === Distributing the optimal solver === |
| 74 | |
| 75 | 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. |
| 76 | |
| 77 | == Avoiding mistakes == |
| 78 | |
| 79 | 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. |
| 80 | |