4 ms·
It 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 o
by hvdijk 4y ago
It 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 4y 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 4y 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 4y 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 4y ago"Trillion" has two meanings. I'm Dutch, we use the traditional meaning of 10^18, what you call quintillion :)