# Calculating "The Devil's Algorithm"



## 930913 (Jun 17, 2012)

God's algorithm, defined as an algorithm that will solve any cube.


A given sequence of moves, if repeated enough times, will return the cube to the original state.
The number of repetitions needed to return to the original state, multiplied by the QTM of the sequence, gives how many states the cube traverses.
A sequence can be found, that traverses every state of cube.
This sequence is God's algorithm, as defined above.

So "F" needs 4 repetitions to return to its original state, giving a traversal of 4 states.
"F U F' U'" needs 6 repetitions to return to its original state, giving a traversal of 24 states.
"F y" or "F R B L" has a traversal of 1440.

So my theory is, find the biggest number, and you should have God's algorithm, assuming one exists.

Thoughts?


----------



## KingTim96 (Jun 17, 2012)

seems really interesting, if this could work, that would be awesome.


----------



## Noahaha (Jun 17, 2012)

I'm no expert on group theory, but I believe the only alg that accomplishes this is called the devil's algorithm, which when performed once on a cube cycles through all 43 quintillion positions. Usually God's alg/number refers to the minimum number of moves to solve the cube.


----------



## 930913 (Jun 17, 2012)

Noahaha said:


> I'm no expert on group theory, but I believe the only alg that accomplishes this is called the devil's algorithm, which when performed once on a cube cycles through all 43 quintillion positions. Usually God's alg/number refers to the minimum number of moves to solve the cube.


Meh, what's in the name? 
We must call things differently in my part of the world 

Anyway, who's up for calculating the shortest algo?


----------



## tasguitar7 (Jun 17, 2012)

Well, doing this by brute force is unfeasible given the number of states of the cube. Now, I have watched videos and read some stuff on commutators and all of that theory, and I can apply it, however I'm not sure if what I am about to say is entirely correct. It seems possible to do essentially "arithmetic" with the members of the set of the cube. For instance you have F, and the cycling effect of F, and R, and the cycling effect of R, so you then add F and R to get F R, and then you observe its cycling effect. So, using this and some other nuggets of thought that I don't have, is it possible to systematically or asymptotically move toward the devil's algorithm?

devil's alg = alg that starts at solved, goes through every state once, ends at solve
god's alg = optimal solution for any specific case

Btw, for a very new user, this is an extremely high quality first thread and first post.


----------



## PM 1729 (Jun 17, 2012)

For 3x3x3 
For 2x2x2
I believe this is what you were referring to, correct me if I am wrong.


----------



## tasguitar7 (Jun 17, 2012)

Wow that's crazy, I didn't know that it had been calculated for 3x3x3. I though it was only 2x2x2 at this point. Do you happen to know how they were calculated? It seems like brute force would have been too large.


----------



## irontwig (Jun 17, 2012)

tasguitar7 said:


> Wow that's crazy, I didn't know that it had been calculated for 3x3x3. I though it was only 2x2x2 at this point. Do you happen to know how they were calculated? It seems like brute force would have been too large.



http://www.speedsolving.com/forum/s...2x2-cube-group&p=690226&viewfull=1#post690226

Just ask Bruce, I guess.


----------



## Stefan (Jun 17, 2012)

tasguitar7 said:


> I didn't know that it had been calculated for 3x3x3



You said you want the shortest algo, allowing repetitions. I doubt Bruce's alg is that (it could be, but I see no reason why it should).



tasguitar7 said:


> Do you happen to know how they were calculated?



You could read Bruce's pages about it...



930913 said:


> Meh, what's in the name?
> We must call things differently in my part of the world



Well, welcome to our part of the world. I'll ask a mod to rename the thread. We don't need extra confusion about these terms.


----------



## whauk (Jun 17, 2012)

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.


----------



## Stefan (Jun 17, 2012)

930913 said:


> The number of repetitions needed to return to the original state, multiplied by the QTM of the sequence, gives *how many states the cube traverses*



... at most. Because you might visit states multiple times.



whauk said:


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



Very nice. However, he doesn't only consider the states *after* each algo application but also the states visited *during* each algo application. And repeating for example RU' does visit both R and U (or even more trivially, take RR'U).


----------



## whauk (Jun 17, 2012)

oops. should have looked up the meaning of "traverse"


----------



## calebcole203 (Jun 17, 2012)

whauk said:


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



Even if the algorithm wasn't traversing the cube, there is just a small flaw to your proof. 

From your algebra, you assume that your "+" function, which does not add anything but rather composes two moves on the cube (g*a and g*b), is commutative. The only little mistake here is assuming that the composing functions has the same properties as the plus function, since you gave them the same symbol. If we let + be the function that composes two moves on the cube, as you have, then obviously U+R =/= R+U, regardless of them being g*a or g*b, so there still could be a Devil's/God's Algorithm. 

EDIT: I was being stupid. You're right whauk and Stefan.


----------



## Stefan (Jun 17, 2012)

No, his proof is alright. He didn't write
RU=(g*a)+(g*b)=g*b+g*a=UR,
he specifically wrote
RU=(g*a)+(g*b)*=g*(a+b)=g*(b+a)=*g*b+g*a=UR.


----------



## qqwref (Jun 17, 2012)

Yes, there is no full sequence g such that g^a=R and g^b=U for some a and b. This is a pretty clear result and there are a bunch of ways you can explain it - here's another:
- every sequence has a maximum order of 1260 (if the centers are fixed)
- g^a is always one of those 1260 positions (one of which is solved) for any integer a
- performing one of those positions and then another will always give one of those positions, since (g^a)(g^b) = g^(a+b)
- if both R and U are among those 1260 positions, then all sequences like RU, UR, UR2, RUR'URU2R', etc. are among those 1260 positions, and clearly there are more than 1260 of those, so we have a contradiction.


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.


----------



## 930913 (Jun 17, 2012)

tasguitar7 said:


> Btw, for a very new user, this is an extremely high quality first thread and first post.


Thank you. Here's to many more.



Stefan said:


> ... at most. Because you might visit states multiple times.


Good point; I was thinking about a short sequence that doesn't come back on itself - no state can be repeated at either end, or infinite loops occur.



qqwref said:


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


So the question remains, what's the shortest algorithm that we can come up with? (Can we fit it on a single piece of paper with the note "repeat _many_ times"?)


----------



## Stefan (Jun 17, 2012)

930913 said:


> Can we fit it on a single piece of paper with the note "repeat _many_ times"?



Not in a useful way. Like qqwref said, it would still be over 10^16 moves long. You'd need reeeaaally good glasses.


----------



## cuBerBruce (Jun 17, 2012)

I have seen this web site (http://anttila.ca/michael/devilsalgorithm/) that gives a definition for a Devil's Number and a Devil's algorithm that is similar or the same as what's being discussed in this thread.

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. If we allow the Hamiltonian circuit to be completed somewhere in the middle of the sequence, we can find upper bounds for (this definition of) Devil's number below
43,252,003,274,489,856,000.

For example, we can let P=UR, and find a place in my Hamiltonian circuit where URUR occurs. We can start the cycle at that point, and then call the rest of the Hamiltonian circuit Q. So the Hamiltonian circuit is PPQ. Then we can cyclic shift to get the Hamiltonian circuit PQP. We can consider that we just need to repeat PQ, and after the P is executed the 2nd time, we will have done a Hamiltonian circuit. Since PQ has length 43,252,003,274,489,855,998, we have that number as an upper bound for Devil's number.

Of course, larger sequences that can be used for P are easy to find within my Hamiltonian circuit, reducing the upper bound even more.


----------



## CubeRoots (Jun 17, 2012)

cuBerBruce said:


> I have seen this web site (http://anttila.ca/michael/devilsalgorithm/) that gives a definition for a Devil's Number and a Devil's algorithm that is similar or the same as what's being discussed in this thread.
> 
> 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 agree, annoying website. It just has to solve the cube at some point during or after an iteration of the algorithm. Of course, if it had to solve it _after, (not just during), _ some number of iterations then the sequence would have to be 20 moves or less due to the fact that you can get from one state to any other you like in 20 moves or less. I think no such sequence exists to do that, it has to be really long, and go through many different states during it's execution.


----------



## Stefan (Jun 17, 2012)

CubeRoots said:


> I agree, annoying website.



No u

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



CubeRoots said:


> I think [...] it has to be really long, and go through many different states during it's execution



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


----------



## Stefan (Jun 17, 2012)

cuBerBruce said:


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


----------



## CubeRoots (Jun 17, 2012)

Stefan said:


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



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 (Jun 17, 2012)

CubeRoots said:


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


----------



## CubeRoots (Jun 17, 2012)

Stefan said:


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



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 (Jun 17, 2012)

CubeRoots said:


> 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?



CubeRoots said:


> But it was what he was talking about!



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


----------



## CubeRoots (Jun 17, 2012)

Stefan said:


> 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 (Jun 17, 2012)

CubeRoots said:


> 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?


----------



## CubeRoots (Jun 17, 2012)

Stefan said:


> 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 (Jun 18, 2012)

CubeRoots said:


> start, perform sequence, end. all moves are during the execution of a sequence.



Moves yes. States no.



CubeRoots said:


> Mine is clearly better.



Nope, clearly worse.



CubeRoots said:


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



CubeRoots said:


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


----------



## CubeRoots (Jun 18, 2012)

Stefan said:


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



what's not there is clarity


----------



## 930913 (Jun 19, 2012)

Are we sure that there is no solution shorter than the ones suggested above?


----------



## Stefan (Jun 19, 2012)

930913 said:


> Are we sure that there is no solution shorter than the ones suggested above?



This:



qqwref said:


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


----------



## 930913 (Jun 20, 2012)

Are we sure that that is the smallest algorithm possible?


----------



## Stefan (Jun 20, 2012)

Only if it exists.


----------



## mocenigo (Jul 6, 2012)

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 (Oct 26, 2012)

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.


----------



## ben1996123 (Oct 27, 2012)

Thekirbycross said:


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



you're late. devils alg for 3x3 has already been found.


----------



## piece popper (Dec 20, 2012)

Wouldn't it be pointless to have a devils algorithm for the 3x3 since there are so many permutations?


----------



## Swordsman Kirby (Jan 9, 2013)

piece popper said:


> Wouldn't it be pointless to have a devils algorithm for the 3x3 since there are so many permutations?



No one said it'd be useful in practice.


----------



## GracefulMaster (Nov 30, 2015)

whauk said:


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


----------



## shadowslice e (Dec 1, 2015)

GracefulMaster said:


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



Not with matrix multiplication. With that you must have a specific order as AB does not equal BA unless B is the inverse of A or the identity matrix. And we have to use matricies to describe the transformations.

Thus, the cycle length may be the same for the example you provided because they are only length 2. If you try a longer one, you will find that something like R U R' U' does not have the same cycle length as R R' U U' despite bidmas/bodmas/bedmas saying that they would be the same as those acronyms only work for pure algebra with no matricies.

In fact, the only reason U R and R U have the same number is due to the symmetries that the two generators have (ie. Rotated 90 then reflected.)


----------



## guysensei1 (Dec 1, 2015)

GracefulMaster said:


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



Pick up 2 cubes, do UR on one and RU on another and convince yourself that you're wrong


----------



## MoyuFTW (Dec 1, 2015)

Has anyone tried to check whether the one provided works? It's so long...

We have to actually prove that it exists first


----------



## DELToS (Dec 1, 2015)

Well, I did find an alg for 5x5 that you would have to repeat 556,920 times to get it back to the solved state: 
R2 B' D' U Bw2 L Rw2 U' Dw2 Fw2 R2 Lw2 B R L2 Lw L2 R2 F' Fw2 R' Rw Lw D' F2 Dw2 L' D2 Bw' Rw' D2 B Fw2 Rw R' Uw L2 Rw2 Lw F' Fw U Fw2 L' Rw' Uw' U' F2 Dw' Fw' L' U2 Dw' D2 B2 R Uw' Lw2 U' Rw' L2 Dw2 U2


----------



## qqwref (Dec 20, 2015)

Just for anyone who's curious, the highest possible order (number of times to repeat a sequence) on the 5x5x5 is 281,801,520, and one such sequence is B' Dw D2 R' Dw Uw' B Dw' D B' Dw' Uw R B R2 Rw Dw2 Uw2 Fw' Lw' Fw2 Lw Fw Lw Uw' Fw' Lw' Fw2 Lw (source)

Or, Fw F' Rw' R L2 F2 B U2 Dw D' Lw L' R F U (source)


----------



## guysensei1 (Dec 20, 2015)

qqwref said:


> Just for anyone who's curious, the highest possible order (number of times to repeat a sequence) on the 5x5x5 is 281,801,520, and one such sequence is B' Dw D2 R' Dw Uw' B Dw' D B' Dw' Uw R B R2 Rw Dw2 Uw2 Fw' Lw' Fw2 Lw Fw Lw Uw' Fw' Lw' Fw2 Lw (source)
> 
> Or, Fw F' Rw' R L2 F2 B U2 Dw D' Lw L' R F U (source)



What about 3x3 or 4x4?


----------



## Christopher Mowla (Dec 20, 2015)

guysensei1 said:


> What about 3x3 or 4x4?


3x3x3 is 2520. (This goes back to theory about void cube parity.)

For convenience, here's a link to alg.garron of the example alg he provided.
(x R' F2 R2 L' U R B' R2 L F' L' U2 L U)2520


----------



## Sajwo (Dec 20, 2015)

For 4x4 it's 765 765 and for 5x5 281 801 520. Don't know how accurate these numbers are since I didn't calculated that. Found it on Polish forum. If you add rotations, it will be probably twice as that.


----------



## AlexanderGZH (Feb 22, 2016)

whauk said:


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


Should R or U be the superflip position, it can exist. Superflip is the only position(other than solve which is equivalent to doing nothing) in 333 with this commutative property. It's like(for matrices) IX=XI where I is the identity matrix and can only be the identity matrix


----------



## EminentCuber (Apr 17, 2016)

This is a very interesting theory, but I would start trying this with a 2x2.

Secondly, god's algorithm refers to if you solved it like a god, how many moves you would do (the most optimal case.) What you're talking about is actually devil's algorithm, which refers how a devil would solve it (really poorly and lazily.)

If I can show some light, whatever light it is, I would think that devil's algorithm has to be super long (and I mean like, 1 trillion turns) and will most likely appear very random to a normal human and express no pattern at all.

It's going to take a lot of math, headaches and lines of code to figure this one out.

And if you have a 2x2x1 or a floppy cube, something with very few (probably around <20) you could test this theory out on and probably do it manually, without the assistance of a computer.

Devil's algorithm will most-likely have no or, at the very least, very little applications. It will be _absolutely _pointless to use this to solve a Rubik's cube, you're better off just using Ruwix.com.

anyway, good luck with this.
_~EminentCuber_


----------



## bobthegiraffemonkey (Apr 17, 2016)

@EminentCuber: Try reading the thread. It's already been done for 2x2 and 3x3 (as well as some other simple puzzles) and linked to here. Also, judging by your post, you might want to have a look around and read up on some cube theory. The Devil's algorithm isn't supposed to be useful for solving, it's just interesting.


----------



## 00 (Apr 18, 2016)

EminentCuber said:


> This is a very interesting theory, but I would start trying this with a 2x2.
> 
> Secondly, god's algorithm refers to if you solved it like a god, how many moves you would do (the most optimal case.) What you're talking about is actually devil's algorithm, which refers how a devil would solve it (really poorly and lazily.)
> 
> ...



please stop bumping old threads without contributing anything


----------

