A256573 -id:A256573 - cp's OEIS frontend

A257401 God's number for a Rubik's cube of size n X n X n (using the half turn metric).

0, 11, 20

Offset: 1

Peter Woodward, Apr 21 2015

"God's Number" is the maximum number of turns required to solve any scrambled cube. The "Half turn metric" considers a 90- or 180-degree turn of any side to be a single turn. The number is not known for cubes of size larger than 3 X 3 X 3.

God's number has been proved using a brute-force attack for the 2 X 2 X 2 and 3 X 3 X 3 cubes. For the 4 X 4 X 4 cube, it has been proved only that the lower bound is 31, while the most probable value is considered to be 32; solving this by brute force would require checking all the A075152(4) possible permutations of the "Master Cube". - Marco Ripà, Aug 05 2015

Jerry Bryan, God's Algorithm for the 2x2x2 Pocket Cube.
Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, and Andrew Winslow, Algorithms for Solving Rubik's Cubes, in: C. Demetrescu and M. M. Halldórsson (eds.), Algorithms - ESA 2011, 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011, Proceedings, Lecture Notes in Computer Science, Vol. 6942, Springer, Berlin, Heidelberg, 2011, pp. 689-700; arXiv preprint, arXiv:1106.5736 [cs.DS], 2011.
Joseph L. Flatley, Rubik's Cube solved in twenty moves, 35 years of CPU time.
Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge, The Diameter Of The Rubik's Cube Group Is Twenty, SIAM J. of Discrete Math, Vol. 27, No. 2 (2013), pp. 1082-1105.
Jaap Scherphuis, Mini Cube, the 2×2×2 Rubik's Cube.
Speedsolving.com, Rubik's Cube Fact sheet.
Wikipedia, Optimal solutions for Rubik's Cube.

Cf. A256573 (quarter turn metric), A054434 (possible positions), A075152 (possible permutations).

Cf. A079761, A079762, A080601, A080602.

From Ben Whitmore, May 31 2021: (Start)
a(n) = Theta(n^2/log(n)) [Demaine et al.].
Conjecture: a(n) ~ (1/4)*log(24!/4!^6) * n^2/log(n).
(End)

cp's OEIS Frontend

A257401 God's number for a Rubik's cube of size n X n X n (using the half turn metric).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula