7
$\begingroup$

Currently I am studying the Schreier-Sims algorithm. To gain a deeper understanding, I am trying to look into applications of this algorithm, among which its use for solving the Rubik's Cube is perhaps the most famous.

However, it seems that there is not a complete, comprehensive algorithm that uses the Schreier-Sims method to solve the Rubik's Cube. Instead, there are only scattered, fragmentary methods, most of which date back over a decade and do not entirely align with the overall framework of the Schreier-Sims algorithm. Does this mean the problem has not been fully resolved?

Is there any simple introduction of using the Schreier-Sims method to solve the Rubik's Cube? If such a guide is not available, is there any examples where the Schreier-Sims algorithm is applied to similar problems? Thanks a lot.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
12
$\begingroup$

I guess, by "solving the Rubik's cube" you mean expressing arbitrary words in the group as words in the six defining generators.

The Schreier-Sims algorithm computes what is known as a strong generating set of the group, which starts with the given generating set and appends new strong generators as words in the existing strong generators. Having done that it can express arbitrary group elements as words in the strong generators very quickly. You could then use the definitions of the new strong generators to express the element as a word in the original six generators (which is known technically as evaluating a straight line program), but the resulting expanded words will be very long in general.

I tried doing this with ten random elements of the Rubik cube group in Magma. The average length of their words in the 27 strong generators was 33, whereas the average length of the expanded words was about 13 million, which is indeed not very efficient.

There are a number of quick heuristic techniques for shortening such long words, but that's a different story.

Improve this answer
$\endgroup$
7
$\begingroup$

A Mathematica notebook that implements the algorithm is at Solving Rubik's Cube using the Schreier-Sims Algorithm. The Schreier-Sims algorithm is highly inefficient, as explained here.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you very much for all of your answers. They are all very good and very helpful. I am currently reading through them. $\endgroup$
    – Marks
    Commented Jul 10 at 9:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.