|
%I #67 Jun 25 2021 16:23:20
%S 0,11,20
%N God's number for a Rubik's cube of size n X n X n (using the half turn metric).
%C "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.
%C 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
%H Jerry Bryan, <a href="http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Jerry_Bryan__God%27s_Algorithm_for_the_2x2x2_Pocket_Cube.html">God's Algorithm for the 2x2x2 Pocket Cube</a>.
%H Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, and Andrew Winslow, <a href="https://doi.org/10.1007/978-3-642-23719-5_58">Algorithms for Solving Rubik's Cubes</a>, 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; <a href="https://arxiv.org/abs/1106.5736">arXiv preprint</a>, arXiv:1106.5736 [cs.DS], 2011.
%H Joseph L. Flatley, <a href="http://www.engadget.com/2010/08/09/rubiks-cube-solved-in-twenty-moves-35-years-of-cpu-time/">Rubik's Cube solved in twenty moves, 35 years of CPU time</a>.
%H Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge, <a href="http://tomas.rokicki.com/rubik20.pdf">The Diameter Of The Rubik's Cube Group Is Twenty</a>, SIAM J. of Discrete Math, Vol. 27, No. 2 (2013), pp. 1082-1105.
%H Jaap Scherphuis, <a href="https://www.jaapsch.net/puzzles/cube2.htm">Mini Cube, the 2×2×2 Rubik's Cube</a>.
%H Speedsolving.com, <a href="https://www.speedsolving.com/wiki/index.php/Rubik%27s_Cube_Fact_sheet">Rubik's Cube Fact sheet</a>.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik%27s_Cube">Optimal solutions for Rubik's Cube</a>.
%F From _Ben Whitmore_, May 31 2021: (Start)
%F a(n) = Theta(n^2/log(n)) [Demaine et al.].
%F Conjecture: a(n) ~ (1/4)*log(24!/4!^6) * n^2/log(n).
%F (End)
%Y Cf. A256573 (quarter turn metric), A054434 (possible positions), A075152 (possible permutations).
%Y Cf. A079761, A079762, A080601, A080602.
%K nonn,hard,more,bref
%O 1,2
%A _Peter Woodward_, Apr 21 2015
|
