pipette
ESEspañol

Solving Large Rubik's Cubes within a Factor of of Optimal

Jeremy Mrzyglocki, Tomas Rokicki, Maxine Perroni-Scharf, Erik D. Demaine

PreprintClaims a big step

In the authors' words

We design optimized algorithms to solve the Rubik's Cube within moves. This upper bound is asymptotically within a factor of of the known lower bound, which applies to almost all instances. The constant is also the first explicit constant factor for the known upper bound of , where the implicit constant of the previous algorithm was (ten duodecillion). Thus we improve the upper-bound constant by a factor of more than (330 undecillion). Our algorithm runs in time linear in the input size , and uses extra space (beyond the state of the cube). Our implementation is the first practical cube solver to generate solutions of length . Our latest solver outperforms existing solvers for as small as .

Main resultThe abstract does not state a limitation.

In plain words AI summary

The authors designed algorithms to solve large Rubik's Cubes using at most 30.5 n² / log n moves. This result is within 2.37 times the best possible solution for almost all cases. They improved the previous constant from about 10 duodecillion to 30.5. Their algorithm runs in linear time and uses relatively little extra memory.

Written by Kimi K2.5 using only the abstract above. Jev checked that every sentence is supported by the abstract sentences it cites, and removed any that were not. Point at a sentence to highlight its source. 1 sentence was removed for not being supported by the abstract.

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 41 pages, 18 figures, 16 tables. Project page: https://largecubebench.org