3 ms·
Is there hypothetically a single algorithm I can just repeat indefinitely and eventually get a solved cube? I’m guessing no: you need conditional branches othe
by Waterluvian 5y ago
Is there hypothetically a single algorithm I can just repeat indefinitely and eventually get a solved cube?
I’m guessing no: you need conditional branches otherwise your single algorithm would just end up back where you started?
- tzs 5y agoYou definitely need conditional branches. Without conditional branches you would be limited to fixed sequences of cube moves. Fixed sequences of cube moves are reversible and they are deterministic. It follows that for any given fixed sequence S there is exactly one starting configuration C such that applying S to C results in a solved cube.
- myaccount80 5y agoIt’s called Devil’s algorithm but I believe it is not know yet whether it exists or not https://getgocube.com/play/devils-number/ https://getgocube.com/play/devils-number/
- 988747 5y agoSomewhat related: I was playing with cube recently, and, starting with solved state, I started doing sequence of two moves that came to my mind: rotate right side down, then the bottom, clockwise. After maybe a 100-150 repetitions (I did not count, just did the moves mindlessly for couple minutes) I went back to solved state. I wonder if there are more such sequences, and how long it takes to go back to original state. The obvious difference from Devil's algorithm was that the 2x2 sub-cube remained untouched the whole time, only the edges were messed up.
- lupire 5y agoEvery sequence behaves this way (For all sequences S, there exists n_S such that S ^ n_S equals S^0, the starting state.) Proving this is an introductory problem in Rubik's theory. Try it!
- zeroonetwothree 5y agoBecause there are only finitely many states, repeating one move will inevitably get you back to where you started from. Also check out Lagrange’s theorem in group theory
- hvdijk 5y agoIt has to exist: it's a mindbogglingly large but finite number of possible permutations, and to go from any one permutation to any other takes a finite number of moves. Therefore, if you can enumerate all possible permutations in some way, any arbitrary way will do, you have a Devil's algorithm by going through them in that order. The question is not whether a Devil's algorithm exists but what the shortest one is.
- owalt 5y agoWorth noting that the Devil's algorithm is not a sequence of turns you repeat over and over, but one that takes you through every possible cube state. You "abort" it partway through when you reach your desired state.
- hvdijk 5y agoIt is both: it is a sequence of turns that if you repeat them over and over, will take you through every possible cube state. But it is possible that the shortest such sequence is trillions of moves long.
- vikingerik 5y agoThere are 43 quintillion cube states, so "trillions" is understating by at least a factor of 10^6. I'm not sure if the 43 quintillion are reachable in a loop of that many moves, or if you need to backtrack through some states to reach others and thus need more moves than that.
- hvdijk 5y ago"Trillion" has two meanings. I'm Dutch, we use the traditional meaning of 10^18, what you call quintillion :)
- kuboble 5y agoCube state is basically a permutation of pieces and any algorithm applied to the cube is a cycle applied to the permutation. You can't solve any state of a cube with one algorithm the same way as you can't sort any array with a single cycle.
- thenoblesunfish 5y agoIf by "algorithm" you mean a fixed sequence of moves, then the (rusty math alert) I'd think the answer is "no", because then that algorithm would be an element of the Rubik's cube group, which you could apply compose repeatedly with any other element to get the identity. This would imply that the Rubik's cube group is cyclic, and I don't think it is (because it's non-Abelian).
- voldacar 5y agoCorrect, the Rubik's cube group is neither cyclic nor abelian. It is generated by 6 elements, which correspond to quarter turns of each of the 6 faces.
- dunkadunka 5y agoThere is the up-up-down-down method that basically uses only one algo over and over but you still have to rotate the cube after each up-up-down-down before applying the next up-up-down-down. I am sure that is not quite what you meant, but this is what is referred to as the 'using only one algo to solve the rubiks cube' this also only works (AFAIR) for 3x3x3 https://www.youtube.com/watch?v=n7irFvVkLpk https://www.youtube.com/watch?v=n7irFvVkLpk Twistypuzzling produces great Youtube videos for all types of twisty puzzles.