<p>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.</p>
<p>I <em>believe</em> that covers all of the parity issues with the order-N Rubik's cube group, which means this method would generate random cubes <em>uniformly</em> distributed across the group.</p>
<p>This takes <span class="math-container">$O(N^2)$</span> time.</p>

CC BY-SA 4.0
2020-12-10T18:58:05.630Z
2020-12-10T18:58:05.630Z
Craig
<p>Recently I've begun considering how one could generate and solve an <span class="math-container">$n \times n\times n$</span> Rubik's cube for <span class="math-container">$n$</span> 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:</p>
<ul>
<li><p><a href="https://arxiv.org/abs/1106.5736" rel="noreferrer">link 1</a></p>
</li>
<li><p><a href="https://deepai.org/publication/on-algorithms-for-solving-the-rubik-s-cube" rel="noreferrer">link 2</a></p>
</li>
</ul>
<p>Such can be executed in <span class="math-container">$O(n^2)$</span> 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 <span class="math-container">$\Omega(n)$</span> and the diameter of the graph of the group of Rubik's cubes is <span class="math-container">$\Theta(n^2/\log n)$</span>, a naive scramble would take <span class="math-container">$\Omega(n^3/ \log n)$</span>, which is not at all feasible. Given that, is there an algorithm for scrambling large Rubik's cubes which:</p>
<ol>
<li>Takes <span class="math-container">$O(n^{2+\epsilon})$</span> time</li>
<li>Produces every possible reachable configuration with positive probability, and only produces such configurations</li>
<li>Is not extremely skewed</li>
</ol>

CC BY-SA 4.0
2020-12-08T09:30:22.513Z
Can you specify what a "randomly executed move" is, and why it takes $\Omega(n)$ time?
smapers
<complexity>
Generating a pseudo random Rubik's cube in $O(n^{2+\epsilon})$ time
Daniel Monroe
# Generating a pseudo random Rubik's cube in $O(n^{2+\epsilon})$ time

(Asked by: username_0 on 2020-12-07)

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](https://arxiv.org/abs/1106.5736)
* [link 2](https://deepai.org/publication/on-algorithms-for-solving-the-rubik-s-cube)

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

**Tags:** complexity

> **Comments:**
> **username_1**: Can you specify what a "randomly executed move" is, and why it takes $\Omega(n)$ time?  

---

## 1 answers

### Answer by username_2 on 2020-12-10. Score: 6 | Accepted 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.


---

