Hacker News Reader

Comment by Waterluvian | Hacker News Reader

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?

View on HN

If 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).

Correct, 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.

It’s called Devil’s algorithm but I believe it is not know yet whether it exists or not

https://getgocube.com/play/devils-number/

Somewhat 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.

Every 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!

Because 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

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.

Worth 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.

It 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.

There 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.

"Trillion" has two meanings. I'm Dutch, we use the traditional meaning of 10^18, what you call quintillion :)

There 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

Twistypuzzling produces great Youtube videos for all types of twisty puzzles.

You 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.

Cube 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.

Reply on news.ycombinator.com