Rubik NxNxN Cube Solution Algorithm

Question

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

I know how to solve cubes larger than 3x3x3:

• First we need to solve the central (flat) fields of the cube so that they look like in the picture.

• Secondly, we will solve the edges:

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

---

It sounds very simple, but the problem is that the methods for solving centers and edges depend on the size of the cube. For the 3x3x3 algorithm for solving centers and edges, it has 0 moves, for 4x4x4 it is longer, and for 5x5x5 it is even longer.

But how can I calculate these steps? Is there an easy way?

Thanks in advance!

Answer 1

You can see this as an exercise in group theory, considering each kind of movement as a permutation. Then you need to find out if the scrambled cube order is the product of some of the available permutations in some order, and if so, which order.

It turns out that there are algorithms for this, as well as some very complex and computer packages that implement them. For packages and themes, one starting point is http://en.wikipedia.org/wiki/Computational_group_theory .

One reference to the algorithm being implemented is to Knuth at http://arxiv.org/pdf/math.GR/9201304.pdf . I have implemented a version of this, so that it is doable, but the paper is very thick - see My link to it Regarding the approach to solving the jigsaw puzzle. If you know more group theory than I do, you can read even more dense documents and apply more efficient algorithms. Oh, if you are working on paper, you can first find out if the problem is solvable, and then theoretically find the sequence of permutations that solves it, but this sequence can be impractically long.

This particular algorithm is not completely different from the scheme described above in that it searches for combinations of available moves that hold some of the objects by rearranging the fixed one, while restoring one other object to the right place.