2026-09-21T03:27:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25750 2026-09-05T19:25:55Z ddc:004 open_access

A Demigod’s Number for the Rubik’s Cube Merino, Arturo Subercaseaux, Bernardo Diameter Rubik’s Cube Experimental mathematics It is by now well-known that any state of the 3× 3 × 3 Rubik’s Cube can be solved in at most 20 moves, a result often referred to as "God’s Number". However, this result took Rokicki et al. around 35 CPU years to prove and is therefore very challenging to reproduce. We provide a novel approach to obtain a worse bound of 36 moves with high confidence, but that offers two main advantages: (i) it is easy to understand, reproduce, and verify, and (ii) our main idea generalizes to bounding the diameter of other vertex-transitive graphs by at most twice its true value, hence the name "demigod number". Our approach is based on the fact that, for vertex-transitive graphs, the diameter at most twice the average distance (of which we give a much simpler proof than in the literature). Then, by sampling uniformly random states and using a modern solver to obtain upper bounds on their distance, a standard concentration bound allows us to confidently state that the average distance is around 18.32 ± 0.18, from where the diameter is at most 36. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arturo Merino and Bernardo Subercaseaux 2026 Is Part Of LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2026.31 urn:nbn:de:0030-drops-257505 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.31 eng https://creativecommons.org/licenses/by/4.0/legalcode