Is there (or can there be) a general algorithm to solve Rubik's cubes of any dimension?

Question

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

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/

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:

• Solving Rubik's cube and other permutation puzzles

Answer 1

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.

Answer 2

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!

Answer 3

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.