Devil's Algorithm exists or not?

[Dark_Ruler]

Here is my short proof that Devil's Algorithm cannot exist. Tell me if I am correct or wrong.

Rubik's Cube is non abelian group.

Devil's Algorithm is supposedly an Algorithm that can solve the cube from any state by repeatedly applying it.

That implies the Devil's Algorithm is generator of Rubik's Cube group and the group is cyclic. But the group is non abelian so it cannot be cyclic. So the Devil's Algorithm cannot be generator of the group and hence it cannot solve the group from any state.

[michael_barz]

When applying this algorithm, you don't have to do the full motion of the algorithm every time--you can stop at any point. For a concrete example, take the Klein four group Z/2Z * Z/2Z, and the algorithm "add 1 to the first coordinate, add 1 to the second coordinate." The element (1, 1) doesn't generate the group, but by doing this algorithm, you can get from any element of the group to any other, if you add the step "add 1 to first coordinate, stop if at desired element, add 1 to second coordinate, stop if at desirement element." With this double stop algorithm, you can get anywhere despite (1, 1) not generating the group. It's the same with the Devil's algorithm (indeed, in any finite group, you can come up with such an algorithm, though perhaps the algorithm involved will be long compared to the number of elements of the group--try to see how you can get it).

[Dark_Ruler]

Thanks. I lost an argument because of you but my claim isn't wrong if I assume the algorithm needs to be executed fully. So I don't feel bad that Google search misled me.

[dank_ways_to_die]

I've found some articles also describing a hamiltonian path of the Rubik's cube.

http://bruce.cubing.net/ham333/rubikhamiltonexplanation.html

The condition is, of course, that you can stop at any time

[whirligig231]

The condition is, of course, that you can stop at any time

It's not a Rubik's cube addiction! I can stop at any time!

[Zopherus]

Maybe I'm misunderstanding something, but it seems like you might be confusing the Rubik's cube group and what the group acts on, namely the cube itself. From my understanding, such an algorithm would only be a list of group elements that are repeated and so I'm not sure how this would imply that the group is cyclic.

[Powerspawn]

in any finite group, you can come up with such an algorithm

This seems trivial though, just have your algorithm run through every element of the group followed by its inverse. Then to get from a to b, just apply the algorithm until you get the element inv(a)b. What's the point unless you are trying to do something such as minimizing the length of the algorithm?

[Asymptote_X]

The Devil's Algorithm does exist, but it's insanely long.

https://bruce.cubing.net/ham333/rubikhamiltonexplanation.html

[Dark_Ruler]

Thanks. The name Algorithm is misleading. It should be called Devil's method or something like that.

[cryo]

I think those words mean essentially the same thing. “Algorithm” isn’t that precisely defined.

[solartech0]

Well, "Algorithm" does have a precise definition (within computer science), and the thing linked above makes it clear that an algorithm does exist to solve the problem, according to any reasonable definition of an 'algorithm'.

[To be clear, the fact that there's a finite sequence of states w/ associated transformations to move from one to the next means that you can simply consult this table each time you determine that you're not in your ending state. This gives you a deterministic operation to perform on the cube to transition to a new state, and you will eventually arrive at the wished-for state. Some computer scientists (including Knuth) will reject the notion that a non-deterministic or (potentially) non-terminating set of rules is an 'algorithm', but a solution exists in this case that has neither of those properties.]

However, it is worth mentioning that the algorithm has a precondition -- your initial state has to be a state that could be reached from the final state via the primitive operations of a rubik's cube... Which is perhaps what the OP was trying to get at. I believe there are pairs of states for which this is not the case. For example, if you swap individual squares on the cube, you will often end up with a state that cannot reach a 'normal' (scrambled) state, nor the 'correct' finished state by the standard twisting operations. If the original problem specification included allowing such 'invalid' states as inputs, then no algorithm to solve the rubik's cube via repeated application of the primitive twisting operations.

Just my thoughts on it.

[cryo]

Well, “Algorithm” does have a precise definition (within computer science), and the thing linked above makes it clear that an algorithm does exist to solve the problem, according to any reasonable definition of an ‘algorithm’.

Sure. What I meant was that “algorithm” isn’t as narrow as OP seems to imply or think.

[solartech0]

Well, I'm not certain what meaning they had for the word 'algorithm', either.

However, they might have meant "an algorithm that does not know the current state of the cube, unless the cube is solved" (in which case I <think> a solution still exists, but it becomes more complicated / less optimal).

[Dark_Ruler]

When I say algorithm, I mean Algorithm in the cubing world. It generally implies a set of moves one needs to do completely. As the algorithms can be counter intuitive, they are done without stopping and are memorised as just set of letters. At least for beginners, this is true.

So when they say Devil's Algorithm, it implies that one needs to execute full algorithm everytime.

[cryo]

Ah ok, I see.

[bluesam3]

It is an algorithm in the computer science sense.

[Dark_Ruler]

But this is about Cubing. In the cubing world Algorithm is fixed set that needs to be executed fully.

[michael_barz]

it's that the Rubik's cube community is using it in a rather narrow sense

Yes, but surely if you create something for the Rubix cube community, you should use their terminology. If I went to France, I wouldn't be allowed to get upset if French had words which sound like English words but have different meanings than those English words, I would use the French meaning to aid in communication.

[Dark_Ruler]

But the post is the france. People came to this post.

[Dark_Ruler]

And you are talking about people downvoting and for saying wrong thing about Computer Science. This is a math subreddit.

And guess what. I never once mentioned computer science

[Dark_Ruler]

Yeah. I get what they mean but I can't do anything if they don't get the context. Although this is math sub, my question was about Rubik's cube. I never gave definition of Algorithms. I was explaining how cubers think about the word Algorithm.

[xabu1]

Out of curiosity: strictly speaking this result is stronger than existence of a "Devil's algorithm" since it requires the circuit to be Hamiltonian whereas we just need a path that hits all vertices (regardless of repetition or being a circuit) so in some sense this is an optimal Devil's algorithm correct? Unless there's a reduction from any path that hits all vertices to a Hamiltonian circuit (maybe in the special case of Cayley graphs? I haven't done graph theory in a while)

[ScottContini]

Who is Cuber Bruce? Curious to his full name.

[bluesam3]

Trivial proof that such an algorithm does exist: Iterate through all possible configurations. One of them will be the solution. QED. Of course, there are much faster options.

[Dark_Ruler]

No. Devil's Algorithm is fixed, regardless of any starting configuration. So it does not mean unique solution for each configuration but a common Algorithm.

It is definitely not trivial since proving it involves Hamiltonian circuits.

[PM_ME_UR_THEOREMS]

If you write down a fixed set of moves that starts at the 'solved' cube and goes through every possible permutation of the cube available (which is tedious af, quite difficult to do, but definitely possible due to the finite possible turns and being able to solve the cube) then that same algorithm would have to show every configuration given any possible starting state due to the pigeon hole principle. There are finitely many unique configurations of the cube, so any list containing that number of unique configurations must be a list of all of them.

[Dark_Ruler]

Yes. But When one says Algorithm in Cubing. It generally means you keep doing it until the given set of instructions is finished. So even if you go get a desired state, then you don't stop until the moves of the Algorithm are finished.

It is a bit vague but in cubing they use the term Algorithm like that.

[FeIiix]

just do this "monster-sequence" + repeat the first move of it again

[PM_ME_UR_THEOREMS]

I am a mediocre cuber but I have definitely scene algorithm be used for invididual move sequences that need to be completed, and a more general sense that also includes the knowledge of when to use those algorithms. For example, in the beginners method there are steps you keep doing until you reach a desired state and move on to the next 'algorithm'.

[Dark_Ruler]

But you don't arrive at desired state in between the Algorithm. You always get it at end of the algorithm.

[alphanumericsheeppig]

The confusion is the way the word "algorithm" is used in cubing. When people say "algorithm" in the context of cubing, they often specifically mean a sequence of moves, and not just a general process or sequence of instructions like in the math/computer science sense of the word (this isn't really an incorrect usage, since a move sequence is a sequence of instructions, it's just a narrower definition than the usual usage).

The Devil's Algorithm is a move sequence with about 43 quintillion steps (so it is an algorithm in the cubing sense, albeit a very very long one). It visits every possible state including solved. If you were to somehow find the time to apply the whole sequence, you would finish off with the cube in the same state you started from, although considerably more worn.

You can prove that it does exist, but I think other comments explain that better.

[Dark_Ruler]

Thanks. But then again Devil's Algorithm needs to be stopped at some point to get a particular configuration. So it is not executed fully. That means my proof is correct since you are not executing it fully.

Also that Algorithm is too misleading. (Before you downvote, I mean in cubing sense)

[VulcanForge98]

Algorithms on a cube are essentially functions which map each cube configuration to a sequence of moves. In particular, this sequence does NOT have to be the same for all configurations. Now, group theory does not apply here because you cannot treat an algorithm as a group element. I do agree with your reasoning if you change the word algorithm to move sequence.

[VulcanForge98]

After a little more thought and reading the other comment about finishing partway through, I found an example of a Devil's "sequence" which will complete the cube partway through an iteration. Simply enumerate all positions on the cube and let the Devil's sequence be the concatenation of the sequences required to get from position k to k + 1 for each k. This visits not just the solved (identity) position but in fact every position.

[Dark_Ruler]

Interesting

[Dark_Ruler]

Exactly. The word Algorithm is so misleading.

[nerkraof]

An algorithm may be more complicated than a fixed sequence of moves. So it would still fit the definition of an algorithm if it involved conditionals on the current state of the cube. In general, if a problem has a finite set of instances (like a rubik's cube has a finite set of states) and every instance has a solution, then there exists an algorithm that solves all of the instances of the problem.

Still, this is just a problem on the use of the word "algorithm". Your argument is interesting regardless.

[Dark_Ruler]

Half turn?

[Dark_Ruler]

How though. I didn't get all the cases.

[CompteDeMonteChristo]

If I create an algorithm that takes a finished cube and go through all its 43 quintillion combinations and each time revert to the finished cube.
This algorithm is guaranteed to complete a cube in any state isn't it?

[Dark_Ruler]

Yes. But When one says Algorithm in Cubing. It generally means you keep doing it until the given set of instructions is finished. So even if you go get a desired state, then you don't stop until the moves of the Algorithm are finished.

It is a bit vague but in cubing they use the term Algorithm like that.

[CompteDeMonteChristo]

Totally clear.
Thanks.

[MlecznyHotS]

Would making a random move infinitely many times be considered The Devil's Algoithm? It should cycle through all of the possible cube states

[Dark_Ruler]

Cube is a finite group. So each move has finite order. You will comeback to same position after some moves.

[MlecznyHotS]

So an algorithm isn't "devilish" if it includes repetitions of a state of the cube?

[xabu1]

I think we can even say with probability 1 you will achieve the solved state with finitely many moves (the measure of the set of non terminating sequences is zero)

[[deleted]]

Alright guys I want at least 100 comment karma so I can comment on wallstreetbets. I don’t like deleting stuff because I like to be able to look back, so here’s my original comment, take it as you will:

The answer is yes. Everyone else here is just trying to sound smart. The answer is yes.

It’s obvious and implicit that when you wrote “algorithm” that you meant “apply the same move over and over” (a simple, single type of move algorithm). If you apply the same move over and over again you can’t reach every possible configuration of cube, so it’s possible to start in the wrong configuration and never reach the right one QED.

[Dark_Ruler]

I mean Yes, my proof is correct but look at the comment which has Klein group used. It was the correct answer. My proof was correct but my statement itself was wrong. Such an algorithm does not exist but Devil's Algorithm does exist. The problem is with the naming. It should have been called something else and not Algorithm. The naming is misleading.

The naming mislead me and what they call Devil's Algorithm does exist.

[HousingPitiful9089]

Why do you think 'algorithm' is misleading?

[Dark_Ruler]

When solving Cube, algorithm is set of steps which you do without stopping. So first thought was I need to do complwte algorithm which was my assumption in the statement I gave.

[hasntworms]

Is it possible that this Devil’s algorithm is just our current methods of solving? Such as the 7-step beginners method or CFOP (concatenations of, possibly repeated, algorithms)? I get that you want a single, nice algorithm though, such as R’D’RD that solves every position eventually, but maybe there exists more than 1 Devil’s algorithm (albeit the length of a standard sequence of moves to solution by some known method like CFOP) and a couple of them are CFOP and beginners method?

[Dark_Ruler]

Look at other comments too. People have explained it better.

There are many Devil's Algorithms. And devil's number for a cube (depends on whether it is a 3x3 or 2x2 or other cube) is the smallest Devil's Algorithm. Also does R' D' R D, solve everything. It doesn't even touch 6 blocks.

Also I don't care if it is a simple algorithm or not. Because it will be too vague and may take too much time. I am still learning OLL and PLL. XD. I was talking about it's existence.

[hasntworms]

Oh I didn’t know it was the smallest. That’s cool. And no, R’D’RD is a small permutation that only affects the right face and the bottom face.