10 ms·
The shortest implementation of solving algorithm is a stack of taken moves while shuffling which just should be reversed one by one.
by madmaniak 8y ago
The shortest implementation of solving algorithm is a stack of taken moves while shuffling which just should be reversed one by one.
- ghubbard 8y agoUnless you scramble the cube using more than 20 moves. http://www.cube20.org/ http://www.cube20.org/
- Systemic 8y agoThe comment you're replying to mentioned the shortest implementation, as in the size of the program written to solve the problem. I believe you're talking about the the optimal shortest path to the solution, which while true, relevant and interesting, isn't contrary to the point.
- mnr 8y agoYou could have shuffled it into a position where it takes less moves to solve than you made while shuffling.
- jfoutz 8y agospecifically, rotate one face one quarter turn 3 times. a replay will undo all 3, but the optimal move is to continue the rotation one more quarter turn. (as the degenerate case for a solution being better than unwinding the move stack.)
- aidos 8y agoMore interestingly, the cube is always 20 moves away from a solution, not matter how much you've mixed it up.
- rimliu 8y agoNitpick: cube is at most 20 moves away from the solution. There may be cases when less moves a needed :) https://en.wikipedia.org/wiki/God%27s_algorithm https://en.wikipedia.org/wiki/God%27s_algorithm
- aidos 8y agoThat's definitely a legitimate nitpick!
- Someone 8y agoNitpick: aidos is right. The cube is always 20 moves away from a solution (but that solution typically isn’t the fastest possible (the 20 is in face turns, not quarter turns, so you can always add extra turns to the optimal solution to make the solution take 20 turns))
- iliis 8y agoThat might very well be, but is it obviously so? What if there was a position that takes 19 moves to solve in the fastest way possible but the next-best solution takes 21 moves? Is there always a solution that takes an even number of steps?
- Someone 8y agoYes, there is. If the last turn is a quarter turn, replace it by a half turn and a quarter turn in the other direction. If it is a half turn, replace it by two quarter turns.
- r_c_a_d 8y agoHe said the shortest implementation, not the shortest execution. I think he meant that the easiest solver to "code" is to just remember the scramble and reverse it. You can see from the videos that it is not doing that though. The solution is not the trivial reverse of the scramble.
- mnr 8y agoAh, I misread. Makes enough sense!
- PDoyle 8y agoThat depends on whether you think "unscrambling" counts as "solving".