17
$\begingroup$

This is a question about Rubik's Cube and generalizations of this puzzle, such as Rubik's Revenge, Professor's cube or in general the $n \times n \times n$ cube.

Let $g(n)$ be the smallest number $m$, such that every realizable arrangement of the $n \times n \times n$ cube can be solved with $m$ moves. In other words, this is the "radius" of the Cayley graph of the $n \times n \times n$ cube group with respect to the canonical generating system.

We have $g(1)=0$, $g(2)=11$ and - quite recently - in 2010 it was proven that $g(3)=20$: God's number is 20.

Question. Is anything known about $g(4)$ or $g(5)$?

I expect that the precise number is unkwown since the calculation for Rubik's cube already took three decades. Nevertheless, is there any work in progress? Are any lower or upper bounds known?

I would like to ask the same question about $g(n)$ for $n>5$, or rather:

Question. Is anything known about the asymptotic value of $g(n)$?

Improve this question
$\endgroup$
4
  • 6
    $\begingroup$ Perhaps it should be mentioned that this result is for the half-turn metric. In light of the comments at matthewkahle.wordpress.com/tag/gods-number, it appears that the situation for the quarter-turn metric will prove to be more elegant mathematically, where the answer is expected to be 26 with a unique position requiring 26 moves to solve. (Also, why restrict to three dimensions? Let's ask for the asymptotics for God's number for the n^k cube). $\endgroup$
    – Peter McNamara
    Commented Oct 11, 2011 at 20:19
  • 2
    $\begingroup$ Thanks Peter; I didn't know that 20 refers to the half-turn metric. And now I'm rather disappointed that the number for the quater-turn metric (which seems much more natural to me) is still unknown! $\endgroup$
    – Martin Brandenburg
    Commented Oct 12, 2011 at 12:29
  • $\begingroup$ An estimate for God's number for the 4x4x4 cube was around 30, in a cubing forum. $\endgroup$
    – user50630
    Commented May 10, 2014 at 1:55
  • $\begingroup$ I'd also be interested in God's number for higher dimensional Rubik's cubes, see: en.wikipedia.org/wiki/N-dimensional_sequential_move_puzzle $\endgroup$
    – Max Lonysa Muller
    Commented Apr 26, 2022 at 13:55

2 Answers 2

Reset to default
16
$\begingroup$

I am not an expert, but I remember seeing this press release from MIT not too long ago. The corresponding arXiv article should answer your second question.

Improve this answer
$\endgroup$
3
  • 15
    $\begingroup$ Just to make the answer to Q2 explicit: $g(n)= \Theta(n^2 / \log n)$. $\endgroup$
    – Joseph O'Rourke
    Commented Oct 11, 2011 at 17:36
  • 1
    $\begingroup$ This is fantastic! I will try to read the paper. This indeed answers Q2. I should have asked Q1 separatedly. $\endgroup$
    – Martin Brandenburg
    Commented Oct 11, 2011 at 19:56
  • 2
    $\begingroup$ Erik Demaine mentioned this result last week at his public lecture "Geometric puzzles: Algorithms and complexity" in the Joint Meetings. math.harvard.edu/~elkies/Pix/jmm12/demaine5.jpg $\endgroup$
    – Noam D. Elkies
    Commented Jan 14, 2012 at 20:09
8
$\begingroup$

Based on this discussion from 2015, God's number for the 4x4x4 cube lies beween 35 and 55 (inclusive) for the outer block turn metric, with the corresponding bounds being 32 and 53 for the single slice turn metric, and 29 and 53 for the block turn metric. Scroll down to the comments for the optimal bounds.

The choice of metric is irrelevant for the asymptotic results of Demaine, Demaine, Eisenstat, Lubiw and Winslow which gives $\Theta(n^2/\log(n))$ as the answer to question two.

Since this question was first asked, cube20.org claims to have also shown that God's number for the quarter turn metric is 26.

As for the 5x5x5, one can find this post claiming an upper bound of 130 for the outer block turning metric.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .