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:

link 1

link 2


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:

Takes $O(n^{2+\epsilon})$ time
Produces every possible reachable configuration with positive probability, and only produces such configurations
Is not extremely skewed
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.