36
$\begingroup$

I love solving Rubik's cube (the usual 3D one). But, a lecture by Matt Parker at the Royal Institute (YouTube Link) led me to an app that can simulate a four dimensional rubik's cube. But unfortunately it was so complex, that I soon got bored as I failed to solve it.

The website to the 4D cube : http://superliminal.com/cube/cube.htm

4d cube

Following which today, I also found an app that can simulate a 5D cube!!

The website to the 5D cube: http://www.gravitation3d.com/magiccube5d/

5d cube

So, my two questions are :

  1. Is there a general (non brute-force) algorithm that can be used to solve a well-scrambled cube of any dimension (even though it may not be very efficient, but yet is not a simple search over all the available space of move sequences) ? [Point modified after reading @RavenclawPrefect's answer :D ]
  2. Mathematically, what is common in all these cubes, and "hypercubes"?

NOTE: By dimensions I mean physical dimension and not the number of rows of pieces on a face of the cube. So a four-dimension cube is a cube in x,y,z,$\delta$ dimensions where $\hat x,\hat y,\hat z,\hat \delta$ are mutually orthogonal unit vectors in the respective dimensions.
For example, here is how the aforementioned 4D cube moves: https://miro.medium.com/max/2552/1*ga32DoV_Hc6e8t6PC1hFHw.gif


Addendum:
List of resources that may help finding an answer to this question:

$\endgroup$
3
  • 2
    $\begingroup$ easy way to solve all rubik's cubes is to reverse the steps you use to scramble the cube... but if you lose the sequence, the problem becomes much more difficult. $\endgroup$
    – tp1
    Commented Nov 28, 2020 at 7:28
  • 2
    $\begingroup$ I think that once you get to side (perhaps side six or seven may be necessary) five you exemplify all the kinds of orbits you can have for the individual cells. If you can solve the orbits in such a way that you can solve the ring they belong to, you can build an algorithm - I think that is how I did five by five when I knew how to do these things. $\endgroup$ Commented Nov 28, 2020 at 7:54
  • $\begingroup$ I think I remember reading somewhere that n dimensional or n x n algorithm is np hard, if that's useful? $\endgroup$ Commented Nov 29, 2020 at 13:16

3 Answers 3

45
$\begingroup$

The algorithmic problem is a special case of ``constructive membership test in permutation groups'' -- given a permutation (you label every face of the cube with a number, then every slice rotation corresponds to a permutation of the numbers, as does the mixed state), write it as a product of generators. This does not care for the dimension of the cube you work in, you just get more and more labels.

The generic solution to the problem is called the Schreier-Sims algorithm (https://en.wikipedia.org/wiki/Schreier–Sims_algorithm). However in its naive form, it produces very long solutions (length >100k for the $3\times3\times 3$ cube).

One can add heuristics (basically to pre-seed with short products as "extra" generators), see for example: https://doi.org/10.1006/jsco.1998.0202 . With such heuristics, the $3\times3\times 3$ cube gets solutions of length $\sim 40-100$, so a magnitude too large, but not astronomically so. One can tune heuristics (use more memory) to get better solutions, though the only (known) way to find a shortest solution is brute-force.

$\endgroup$
16
  • 2
    $\begingroup$ Although interesting, this does not produce a general solution for arbitrary cube dimension. It is just a general heuristic algorithm to find reasonable solutions for specific cube dimension and specific size. It cannot even produce a general solution for the general $n×n×n$ cube, unlike the commutator-based approach. That said, one has no choice but to go this route for permutation puzzles in full generality, since any solution for a specific kind of puzzle would be ad-hoc. $\endgroup$
    – user21820
    Commented Nov 28, 2020 at 16:55
  • 5
    $\begingroup$ @user21820 I am not sure that I understand what you are saying here. It would be possible in principle to write an algorithm $\mathtt{Cube(n,pos)}$ that would take as input a permutation representing a possible position of an $n \times n \times n$ cube, and return a word in the generators of the group. The hardest part might be working out what the generators are, but it could be done. You could then use Schreier-Sims together with heuristics to shorten words. Of course it's performance would probably decline rapidly with increasing $n$, but it would be a general solution of the problem. $\endgroup$
    – Derek Holt
    Commented Nov 28, 2020 at 17:22
  • 4
    $\begingroup$ @user21820 From what I can tell, the quoted Schreier-Sims algorithm is polynomial time. This is followed up with more heuristic methods that can produce better solutions at higher cost, but it's certainly much better than RavenclawPrefect's method, which has no upper bound as stated (because the enumeration could take an arbitrarily long time to hit the solution) and is factorial time with a reasonable choice of enumeration. $\endgroup$ Commented Nov 28, 2020 at 17:39
  • 7
    $\begingroup$ I don't believe that there is any sense in which an algorithm is not an explicit mathematical solution. $\endgroup$
    – Derek Holt
    Commented Nov 28, 2020 at 18:52
  • 2
    $\begingroup$ @user21820 Why would this not be considered an explicit solution? Are you aiming for a small set of rules that one would apply (such as the printed solutions for the $3\times3\times 3$ cube)? I think any such solution will scale rather badly for increasing $n$. $\endgroup$
    – ahulpke
    Commented Nov 28, 2020 at 20:38
35
$\begingroup$

Here is a very simple (and very inefficient) algorithm:

The set of finite sequences of moves is countable, so we can enumerate such sequences $s_1, s_2, \ldots$ (specifically, we can do so in a computable manner). Then execute the following algorithm:

i=1
while cube is not yet solved:
  execute move sequence s_i
  if cube is solved:
    return s_i
  else
    undo move sequence s_i
  i = i+1

Since every finite sequence of moves appears in our enumeration, this algorithm will always terminate in finite time (and in fact for a fixed puzzle with finitely many configurations, its runtime will necessarily be bounded).

For a more "reasonable" algorithm, some kind of bound needs to be put on the runtime; this one is at least exponential in the dimension of the cube, which I suspect is very suboptimal.

Edit: This answer seems to have gotten a lot of attention by virtue of being the earliest one to the question, but the other answers to this question are significantly more interesting; go upvote them instead!

$\endgroup$
3
  • 1
    $\begingroup$ @RavenclawPrefect: You may be interested in my (partial) answer, since it strongly suggests that there should in fact be a humanly understandable general algorithm. $\endgroup$
    – user21820
    Commented Nov 28, 2020 at 16:21
  • $\begingroup$ It’s not really what someone has in mind when they want to see an algorithm. Sure, it’s technically working, but it’s so obvious (and so obviously bad) that it’s not even worth mentioning.. $\endgroup$
    – wim
    Commented Nov 29, 2020 at 14:12
  • 10
    $\begingroup$ @wim: On the contrary, bad algorithms are definitely worth mentioning, if only so that one can formulate the question "Is there a better algorithm?" It's mathematically important to know whether an algorithm of any kind exists. And there are many algorithmically solvable problems where no better algorithm than a "brute force" one is known to exist. $\endgroup$
    – Lee Mosher
    Commented Nov 29, 2020 at 18:31
24
$\begingroup$

Firstly, are you familiar with the commutator-based solution to general permutation puzzles? You certainly can do the same here for each specific dimension and size, and probably can generalize it to arbitrary dimension and size with some effort. It comes down to finding suitable commutators for each of the orbits and showing that parities can be resolved. Here an orbit is a set $S$ of positions such that any piece at a position in $S$ can be moved to every position in $S$ but no position outside $S$. (In group-theoretic terminology, the action of the group of all scrambles of the cube on the cube is transitive.)

While I have not thought about the details, the general idea would be to show the following:

  1. There is some algorithm to make it so that for every orbit $S$ the pieces in $S$ are in some even permutation.

  2. For each orbit $S$, there is some 3-cycle commutator on some positions $P,Q,R$ in $S$ and some algorithm to move pieces at any given positions $A,B,C$ in $S$ to $P,Q,R$ respectively. This lets you perform any even permutation on the pieces in $S$.

  3. For each orbit $S$, I think you can define the orientation of pieces in each orbit such that each face turn does not change their total orientation, and there is some commutator that only changes the orientation of the pieces at some positions $P,Q$ by $+1$ and $-1$ respectively, and some algorithm to move pieces at any given positions $A,B$ in $S$ to $P,Q$ respectively. This would suffice to let you fix the orientation of all pieces in $S$.

Once you establish the above points, you can simply apply them in that order to solve the cube. For example, it is not hard to prove the above points for the 3d cube of arbitrary size, where you use the slice turns to achieve the first point (fixing parity for all orbits), even if it is a little messy. I think it generalizes to arbitrary dimension in a similar fashion.

$\endgroup$
2
  • $\begingroup$ It is taking me time to digest your other post...for the time being, I have added the link to it in the Addendum to my question. Thanks for the answer! $\endgroup$ Commented Nov 29, 2020 at 8:03
  • 1
    $\begingroup$ @CrazyGoblin: You're welcome! If you have any questions about either post, feel free to ask me in comments or in chat. $\endgroup$
    – user21820
    Commented Nov 29, 2020 at 9:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .