2024/04/10 by So Hirata, Hirata, So · 1 citation
Computer Science · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2404.07337
openalex publication_date 2024/04/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The diameter of the Cayley graph of the Rubik's Cube group is the fewest number of turns needed to solve the Cube from the hardest initial configuration. 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 Rokicki 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 probability 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. The probabilistically estimated diameter is shown to obey the approximate formula of ln N / ln r + ln N / r, where N is the number of configurations and r is the branching ratio.