• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Calculating "The Devil's Algorithm"

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
What hasn't been stated clearly is if the last iteration of the sequence must execute the full sequence, or if the Hamiltonian circuit can be completed somewhere in the middle of the last iteration of the sequence.

I think neither this thread's definition nor the page you linked to are concerned about it being a circuit, Hamiltonian or not. And I'd say it's good that way - that page's definitions are very natural and simple (except it should ask for a move sequence rather than a move set, but it's clear what's meant).
 
Last edited:

CubeRoots

Member
Joined
Mar 22, 2012
Messages
538
Location
Leicester, UK
WCA
2012LIVS01
YouTube
Visit Channel
No u

The site is alright. I doubt you even read it. And you apparently misunderstood Bruce. A lot.



As stated/explained in this thread aaand on that site that you find so annoying.

You are argumentative, and wrong. I did read that site, and it is annoying. The first definition is terrible, and the formatting is ugly. Do you have emotional attachment to this site?

Also, notice the part of Bruce's post that I quoted, I wasn't interested in the rest all I was talking about was whether it had to solve after some number of iterations or during the last.
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
The first definition is terrible
Except for the set/sequence issue, I find it really good. What do you find bad about it? Just calling it "annoying" and "terrible" doesn't tell me much. And what's your better definition?

"and the formatting is ugly"
Spoiled much? And I take good content over good style any time (not that I agree about this being ugly).

"Do you have emotional attachment to this site?"
Since I like good stuff, I guess I'll have to say yes. Didn't before today, though, if that's what you mean.

"all I was talking about was whether it had to solve after some number of iterations or during the last."
And that's not what Bruce was talking about. He was talking about completing the Hamiltonian circuit, not about solving.

"notice the part of Bruce's post that I quoted, I wasn't interested in the rest"
I did notice. But the rest of Bruce's post discussed exactly that same thing.
 
Last edited:

CubeRoots

Member
Joined
Mar 22, 2012
Messages
538
Location
Leicester, UK
WCA
2012LIVS01
YouTube
Visit Channel
Except for the set/sequence issue, I find it really good. What do you find bad about it? Just calling it "annoying" and "terrible" doesn't tell me much. And what's your better definition?

"and the formatting is ugly"
Spoiled much? And I take good content over good style any time (not that I agree about this being ugly).

"Do you have emotional attachment to this site?"
Since I like good stuff, I guess I'll have to say yes. Didn't before today, though, if that's what you mean.

"all I was talking about was whether it had to solve after some number of iterations or during the last."
And that's not what Bruce was talking about. So why did you quote him? I'm confused.

A Devil's algorithm is a sequence of moves such that, when iterated on a cube in an arbitrary state, this cube will reach the solved state during some iteration.

I would too, but this site isn't great in either aspect in my opinion...

What I was trying to get at was the fact that you were a bit sensitive to a bit of criticism about that site.

But it was what he was talking about! he wanted to know whether it had to reach solved after a full iteration of a sequence, or whether it could reach it during the last. I Answered his question!
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
A Devil's algorithm is a sequence of moves such that, when iterated on a cube in an arbitrary state, this cube will reach the solved state during some iteration.

That's pretty much the same, except your "during" sounds like it might not count if the solved state is reached *after* an iteration. How is yours supposed to be better?

But it was what he was talking about!

No it wasn't. Check my updated explanation (sorry for the edits).
 

CubeRoots

Member
Joined
Mar 22, 2012
Messages
538
Location
Leicester, UK
WCA
2012LIVS01
YouTube
Visit Channel
That's pretty much the same, except your "during" sounds like it might not count if the solved state is reached *after* an iteration. How is yours supposed to be better?



No it wasn't. Check my updated explanation (sorry for the edits).

Well you can't disinclude the last move from a sequence lol. The last move is as much during an iteration of a sequence as any.
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
Well you can't disinclude the last move from a sequence lol. The last move is as much during an iteration of a sequence as any.

After a move isn't during the move, and after a sequence isn't during the sequence. And states are reached *after* moves. But again, ignoring that, your definition is pretty much the same as the page's. So I guess you find yours terrible as well?
 
Last edited:

CubeRoots

Member
Joined
Mar 22, 2012
Messages
538
Location
Leicester, UK
WCA
2012LIVS01
YouTube
Visit Channel
After a move isn't during the move, and after a sequence isn't during the sequence. Or at least it's reasonable to think so. But again, ignoring that, your definition is pretty much the same as the page's. So I guess you find yours terrible as well?

start, perform sequence, end. all moves are during the execution of a sequence. Mine is clearly better.

Anyway, there are only some small number of cases, around 2000 or less I think, the states that are in the group generated by the sequence, where the cube would be solved straight after an iteration. So if you count the during thing as a flaw, it only means that there are 2000ish or less trivial cases that do not fit with the definition. The definition on the site has the opposite effect: taken literally, the definition only works for these special cases.
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
start, perform sequence, end. all moves are during the execution of a sequence.

Moves yes. States no.

Mine is clearly better.

Nope, clearly worse.

So if you count the during thing as a flaw, it only means that there are 2000ish or less trivial cases that do not fit with the definition.

And that's 2000 too many.

The definition on the site has the opposite effect: taken literally, the definition only works for these special cases.

Nope, it works for *all cases*, during or after iterations, because it doesn't differentiate between those at all. You're reading something into it that's simply not there.
 

930913

Member
Joined
Jun 17, 2012
Messages
5
Are we sure that there is no solution shorter than the ones suggested above?
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
Are we sure that there is no solution shorter than the ones suggested above?

This:

As far as I know, though, there's nothing theoretically stopping us from making a sequence that is about 1/1260 of the length of the full Devil's Algorithm, such that applying the sequence over and over will go through every position at some point (i.e. the sequence 1260 times is its own Devil's Algorithm). It wouldn't help much in practice, though, since it would still be over 10^16 moves long.
 

mocenigo

Member
Joined
Apr 6, 2011
Messages
12
whauk, your argument is correct. I think that a bit of group theory simplifies it. If such an algorithm g existed, then the group of the 3x3x3 cube would be cyclic (generated by one element), in particular abelian (commutative). However, it is not, because for instance RU is not equal to UR.

However, one could ask if there is a sequence of movements g such that any position can be obtained WHILE performing g a given number of times. I.e. g*a times and a prefix of the sequence of movements of g. ONe can prove that the maximal order of an element of the 3x3x3 Rubik Group is 1260, i.e. there is no sequence that will only return to the initial state after strictly MORE than 1260 repetitions. Since the cube has 43252003274489856000 positions, the a lower bound for the length of this algorithm would be 43252003274489856000/1260 = 34326986725785600 moves, which would make it quite difficult to memorize...
 

Thekirbycross

Member
Joined
Oct 9, 2012
Messages
1
What if you a had an algorithm with a traversal of two that would go through half of the possible combinations of a three by three . That seems easier to find.
 
Joined
Nov 30, 2015
Messages
1
assuming your "god's algorithm" g exists:
then R=g*a (repeating gods alg a times, for a certain a) and U=g*b (similar)
so RU=(g*a)+(g*b)=g*(a+b)=g*(b+a)=g*b+g*a=UR
as RU is not the same as UR i prooved that your "gods algorithm" cannot exist.

You do realize that RU and UR are in fact the same. If "U" were 3, and "R" were 2, then UR (3*2) would equal 6. Similarly, RU (2*3) would equal 6.
Also, g*b+g*a is the same as g*a+g*b as bedmas states to do multiplication first.
 
Top