Re: 'Magic Algorithm' for the Rubik's Cube?

I was thinking about something I was reading about Rubik's Cube
algorithms. They are turns of the cube to move certain pieces, and no
matter what it would go back to the original position if you repeated
it enough. This got me thinking... Is there an algorithm that would
always lead to the solved state?

Well, that's exactly what the various published solutions are.

I mean, I know how inefficient it
would have to be: you might have to go through all
43,252,003,274,489,856,000 positions and an average of
21,626,001,637,244,928,000 moves. Oh ya and one other specification
for the algorithm I am requesting: It must be shorter than the amount
of positions the cube can be in.

Okay, so I guess what you mean is, you want a *fixed sequence of moves*,
an "algorithm" that *does not take into account the specific position*,
that is nevertheless guaranteed to reach the solved state no matter what
the initial state was. Which means it must run through all possible
states. And the last requirement effectively means that it must not
repeat any of them. In other words, you're asking for a Hamiltonian
circuit of the 43-quintillion-node graph of all of the possible positions.

I had no idea, so I decided to look it up. If I'd found a solution
on the web, I would just have said so and let people have a crack at
finding it, but <http://web.usna.navy.mil/~wdj/book/node187.html> is
what I actually found, and this page says it's unknown whether this
Hamiltonian circuit exists.
--
Mark Brader "Computers get paid to extract relevant
Toronto information from files; people should not
msb@xxxxxxx have to do such mundane tasks." -- Ian Darwin

My text in this article is in the public domain.
.

Relevant Pages

  • Re: Yet another substitute for Math.random
    ... matter truly random or pseudo-random, given that the tester is truly ... acting on some - possibly very sophisticated - algorithm. ... pseudo-random) then on the long run player B will loose more games ...
    (comp.lang.javascript)
  • Re: What is the accepted technical definition of the word break?
    ... and an algorithm that is too weak because of a successful ... the normal definition of "broken" is ... that an algorithm meets its *claimed* security goals - no matter how weak ... but this is a different matter. ...
    (sci.crypt)
  • Re: quick algorithm to find the neighbours of a sample (2D)
    ... The algorithm will be order N to find the neighbours of a single point ... You can improve this if you want to repeat this performance for many ... then using a binary search to find the range of ...
    (comp.graphics.algorithms)
  • Re: SF: New factoring method
    ... At this point I know it's a matter of quadratic residues ... I wasn't sure what JSH knows. ... but factoring /2 still is not an easy task in general. ... I doubt that JSH has the ability to implement his "algorithm". ...
    (sci.math)
  • Lock-free queue and the correctness of the algorithm....
    ... I have looked again at the following algorithm: ... JMP @@Exit ...
    (comp.programming.threads)