Changes between Version 1 and Version 2 of RubikCubeSolving


Ignore:
Timestamp:
08/13/2008 10:08:48 PM (16 years ago)
Author:
kali
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • RubikCubeSolving

    v1 v2  
    1717 * 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.
    1818
    19 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:
     19And 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:
    2020 1. there is always an even number of edges that are flipped,
    2121 2. the sum of elementary rotation on corner cubies is always a multiple of three,
     
    2424As 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.
    2525
     26== Strategy ==
     27
     28The 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
     30So 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
     37This "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
     47Some of these "moves" are redundant. All of them are "valid".
     48
    2649= Implementing configuration =
    2750
     51Once 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
     55It 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
     57But 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
     59Automatic 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.
     60As we are interested in the opposite process, we will have to inverse the move, but this is a no-brainer.
     61
     62The 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
     69Michael 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
     71The 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
     75We 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
     79As 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
    2881= Links =
     82
     83[http://www.geometer.org/rubik/index.html Tom Davis Rubik program]
     84[http://www.geometer.org/rubik/group.pdf Tom's draft essay on cube group permutations]
     85[http://www.math.ucf.edu/~reid/Rubik/optimal_solver.html Michael Reid optimal solver]