# Generating a pseudo random Rubik's cube in $O(n^{2+\epsilon})$ time

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
• Can you specify what a "randomly executed move" is, and why it takes $\Omega(n)$ time? Dec 8, 2020 at 9:30

## 1 Answer

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.