Probabilistic estimates of the diameters of the Rubik's Cube groups

The diameter of the Cayley graph of the Rubik's Cube group is the fewest number of turns needed to solve the Cube from any initial configurations. For the 2×2×2 Cube, the diameter is 11 in the half-turn metric, 14 in the quarter-turn metric, 19 in the semi-quarter-turn metric, and 10 in the bi-quarter-turn metric. For the 3×3×3 Cube, the diameter was determined by Rikicki et al. to be 20 in the half-turn metric and 26 in the quarter-turn metric. This study shows that a modified version of the coupon collector's problem in probabilistic theory can predict the diameters correctly for both 2×2×2 and 3×3×3 Cubes insofar as the quarter-turn metric is adopted. In the half-turn metric, the diameters are overestimated by one and two, respectively, for the 2×2×2 and 3×3×3 Cubes, whereas for the 2×2×2 Cube in the semi-quarter-turn and bi-quarter-turn metrics, they are overestimated by two and underestimated by one, respectively. Invoking the same probabilistic logic, the diameters of the 4×4×4 and 5×5×5 Cubes are predicted to be 48 (41) and 68 (58) in the quarter-turn (half-turn) metric, whose precise determinations are far beyond reach of classical supercomputing. It is shown that the probabilistically estimated diameter is accurately approximated by ln N / ln r + ln N / r, where N is the number of configurations and r is the branching ratio.