8
$\begingroup$

Recently I've begun considering how one could generate and solve an $n \times n\times n$ Rubik's cube for $n$ well over 10,000. To solve such a cube is feasible; easily implementable parallelizable algorithms to solve such large cubes can be created with the methods listed here:

Such can be executed in $O(n^2)$ time, considering that they rely on short sequences of moves that only displace a couple of cubes, and do not have to compute individual rotations. But scrambling is another story. Given that a randomly executed move takes time $\Omega(n)$ and the diameter of the graph of the group of Rubik's cubes is $\Theta(n^2/\log n)$, a naive scramble would take $\Omega(n^3/ \log n)$, which is not at all feasible. Given that, is there an algorithm for scrambling large Rubik's cubes which:

  1. Takes $O(n^{2+\epsilon})$ time
  2. Produces every possible reachable configuration with positive probability, and only produces such configurations
  3. Is not extremely skewed
$\endgroup$
1
  • 1
    $\begingroup$ Can you specify what a "randomly executed move" is, and why it takes $\Omega(n)$ time? $\endgroup$
    – smapers
    Dec 8 '20 at 9:30
6
$\begingroup$

Well, the easy answer is that you don't traverse the graph of moves, you just generate a random group element directly. A non-face-center cubie in an NxNxN cube will have an orbit of size 8, 12, 24 or 48, with 8 being possible only for corner cuties and 12 only being possible for edge-center cubies with N odd. Divide the cubies into orbits, then generate a random permutation for each orbit with the restriction that the total permutation across all orbits must be even. Then generate orientations for all edge and corner cubies, with a mod-2 parity restriction on each edge orbit and a mod-3 parity restriction on the corners.

I believe that covers all of the parity issues with the order-N Rubik's cube group, which means this method would generate random cubes uniformly distributed across the group.

This takes $O(N^2)$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.