6

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.

Cube with solved centers

  • Second, we solve the edges:

Cube with solved edges

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

4x4x4 cube reduced into 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!

Firzen
  • 1,909
  • 9
  • 28
  • 42
  • This is a really interesting question, but I doubt there's any simple answer to this question (or any answer that would fit in an SO answer). You're probably best off searching Google for some specific algorithms. – templatetypedef Jan 16 '14 at 03:22
  • Why you holt question with upvotes and favourites? Do you really think that I haven't tried googling the algorithm? If all the stackoverflow can do to help me is hold my question, than .. really thanks. – Firzen Jan 16 '14 at 09:17
  • Late comment. For 4x4x4, pairing edges disturbs the center pieces. It would be simpler to pair edges before centers, so pairing edges doesn't require restoring disturbed center pieces. Versus 3x3x3, 4x4x4 introduces new parities, 2 edge pairs can be swapped, and 1 edge pair can be flipped, the centers can be moved. 5x5x5 or larger cubes don't introduce any new parity issues. Sequences similar to 3x3x3 or 4x4x4 can be used for NxNxN cubes. – rcgldr Jul 27 '19 at 05:44

1 Answers1

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.

Community
  • 1
  • 1
mcdowella
  • 19,301
  • 2
  • 19
  • 25