Algorithm for solving NxNxN Rubik's cube [closed]

Question

I want to write cubesolver for Rubik's cube of any size.

I know the way how cubes bigger than 3x3x3 can be solved:

• First we need to solve the center (flat) fields of cube, so they will look like at the picture.

• Second, we solve the edges:

• And finally, we can reduce whole problem to solving 3x3x3 cube:

---

That sounds very easy, but the problem is that ways to solve centers and edges depends on cube size. For 3x3x3 algorithm for solving centers and edges has 0 moves, for 4x4x4 it is longer, and for 5x5x5 it is even more longer.

But how can I compute these moves? Is there any simple way?

Thanks in advance!

Answer 1

You can look at this as an exercise in group theory, by considering each sort of move as a permutation. You then need to find out if the scrambled order of the cube amounts to a product of some of the available permutations in some order and, if so, what that order is.

It turns out that there are algorithms to work this out, and some very sophisticated, and computer packages that implement them. For the packages and the subject one starting point is http://en.wikipedia.org/wiki/Computational_group_theory.

One reference to an implementable algorithm is by Knuth at http://arxiv.org/pdf/math.GR/9201304.pdf. I have implemented a version of this, so it is doable, but the paper is very dense - see my reference to it at Regarding approach to solving sliding tiles puzzle. If you know more group theory than I do, you will be able to read even denser papers and implement more efficient algorithms. Oh - if you work through the paper you should be able to first of all find if the problem is solvable, and then, in theory, find a sequence of permutations that solves it, but that sequence may be impractically long.

This particular algorithm is not completely different from the scheme that you have outlined above, in that it looks for combinations of the available moves that keep some of the objects been permuted fixed, while restoring one other object to its proper place.