this is weird

[myclock]

ok this has happened to me, countless number of times now. once i solve the cube, i try to scramble it up (sometimes without looking) and then only to find out i solved it again :S

can someone expalin how this is possible?

 

[Kenneth]

You are scrambling in a cycle, try to randomly orient the cube every 3-5 turns and it will (probably) not happen anymore.

Many does that, My brother often gets a situation where there is only permutations to do = cycle scramble.

 

[Karthik]

Any set of moves when repeated 'n' times will return the cube to it's original state.
'n' depends on the set of moves you are doing.

 

[AvGalen]

Some small examples just to show how small n can be:
H-Perm: n=2
U-Perm: n=3
F(RUR'U')F': n=6

And sometimes n is quite large
RU: n = 105

I have once read a claim that n is actually never larger than 4360 (I am not really sure I remembered that number correctly and I couldn't find the source anymore). That would mean that if you took a random scramble of 250 moves, the cube would still be solved after applying that random scramble for 4360 times (or less). This is sometimes called "the devils algorithm".

 

[Johannes91]

Bruce Norskog wrote:
Finally, I note that for any alg (for the standard 3x3x3), it's been
proven that there are none with an order higher than 1260.

This is sometimes called "the devils algorithm".

I thought it means a move sequence that visits all positions.

 

[TheBB]

This is sometimes called "the devils algorithm".

I was under the impression that the devils algorithm was a sequence of moves that took you through each possible position, possibly exactly once (can't remember). 250 moves 4360 times isn't nearly enough.

 

[Karthik]

Bruce Norskog wrote:
Finally, I note that for any alg (for the standard 3x3x3), it's been
proven that there are none with an order higher than 1260.

Yes, 1260 is what I had come across.

 

[AvGalen]

OK, so 1260 it is. Can anyone explain that number (probably edge-cycles * corner-cycles)

The explanation that the devils algorithm should take you through every possible position (and thus would be 43,252,003,274,489,856,000 moves long) should be the one and only meaning, but it isn't.

Has it been proven/disproven that the devils algorithm is possible?

 

[Kenneth]

Gustav Fredell also calculated this a while back and got 1260.

n = 60, 120, 180... are common figures.


Hmmm... 35 * 36 = 1260 (does that have something to do with it?)

Edit: an alg that does a 7 cycle edges and a 5 cycle edges, totaly 12 (all) edges affected, has to be repated 7 * 5 = 35 times.

But 36 (6 squared) for corners?

More edit: I just realised it is not possible to get a higer figure than 7 * 5 = 35 for edges, because:

9 cycle + 3 cycle = 27
11 cycle + last edge in place but orients (2 cycle) = 22

Then yo can try 9 cycle + 2 cycle + as above one in place (2 cycle) = 36
Or at the most 2 cycle + 2 cycle... max 6 = 2^6 = 64

But, the 2 cycles will be solved/not solved every second time, no matter how many there are.

Same thing if you do 3 * 3 * 3 or whatever...

 

[TheBB]

Has it been proven/disproven that the devils algorithm is possible?

It's obviously possible if you don't demand that every position be visited only once. If you do, then you're asking if there exists a Hamiltonian circuit on the cube graph, which, to the best of my knowledge, is a notoriously difficult problem, even on small graphs, not to mention the cube graph. And to actually find it, IF it exists, I think is NP-complete, so you might as well give up straight away.

 

[Stefan]

1. NP-completeness talks about decision problems.
2. For a fixed size cube, the answer is constant, thus trivial, thus no NP-completeness.
3. While the general Hamiltonian cycle problem is indeed NP-complete, I'm not sure it's NP-complete if restricted to Rubik's cube graphs.
4. I don't think it's known even for the 2x2x2 whether its graph is a Hamiltonian cycle.