God's Number for 5x5x5?

shadowslice e said:
When a speedcuber begins to solve they will likely add to the number of moves required to reach each state rather than reduce it (at least for a few moves at the start)
Click to expand...

Hmm, I'm not 100% sure what you mean, but you just made me think of something.

God's 5x5x5 number might be higher than God's 5x5x5 number for a random state. In other words, God might be able to save moves by pulling a Steven Brundage.

Consider this one-dimensional 2x2 puzzle with its six states. You have moves U, D, L and R. The top and bottom states have average distance 1.2 moves to all other states. The other four states have average distance 1.6 moves. So on average you can save moves if you declare one of those "mixed" states to be the goal, instead of one of those "nonmixed" states. The maximum distance, i.e., God's number, is the same here for all states (it's two moves), but I can imagine other puzzles (including 5x5x5) having different God's numbers for different goal states.

2x2x0_graph.png
 
Last edited:
nalralz said:
I know there is a thread for God's number for 4x4x4 but but what is God's number for 5x5x5?
Click to expand...

I did a count of possible unique moves made from the solved state as a function of depth and compared that to the number of possible piece arrangements on a Wikipedia page. I can't remember the exact number but I'm sure it was under 60. Here are some numbers from my own 5x5x5 brute force solver:

image.jpg
 
shadowslice e said:
Number of permutations possible for WCA scrambling= 15^60= 3.67x10^70
Click to expand...
Wrong. There are not 18 possible turns, but 36. (And the calculation is quite a bit more complicated than that anyway, because of turns on the same axis.)

Lucas Garron said:
(The fraction of Megaminx scrambles we can generate is also very low.)
Click to expand...
Megaminx scrambling is actually hilariously bad (we can reach less than the *cube root* of the total number of positions), but unfortunately there's probably not much we can do about that... Every better scrambling algorithm takes longer or is harder to do.

Stefan said:
Hmm, I'm not 100% sure what you mean, but you just made me think of something.

God's 5x5x5 number might be higher than God's 5x5x5 number for a random state. In other words, God might be able to save moves by pulling a Steven Brundage.
Click to expand...
Perhaps, perhaps. If so this would have to be because bigcubes do not form groups (due to their indistinguishable pieces). Someone should test this idea on a simpler puzzle with indistinguishable pieces, like the three-color 3x3x3.
 
Stefan said:
Hmm, I'm not 100% sure what you mean, but you just made me think of something.

God's 5x5x5 number might be higher than God's 5x5x5 number for a random state. In other words, God might be able to save moves by pulling a Steven Brundage.

Consider this one-dimensional 2x2 puzzle with its six states. You have moves U, D, L and R. The top and bottom states have average distance 1.2 moves to all other states. The other four states have average distance 1.6 moves. So on average you can save moves if you declare one of those "mixed" states to be the goal, instead of one of those "nonmixed" states. The maximum distance, i.e., God's number, is the same here for all states (it's two moves), but I can imagine other puzzles (including 5x5x5) having different God's numbers for different goal states.

http://www.stefan-pochmann.info/misc/2x2x0_cayley_graph.png
Click to expand...

Would it be fair then to define God's number as the maximum distance between any two states?
 
spyr0th3dr4g0n said:
Would it be fair then to define God's number as the maximum distance between any two states?
Click to expand...

That's already called diameter. And I think "God's number" already is defined as the maximum number of moves needed to "solve" (to a specific "solved state").

Here's another puzzle, one with different average distances and different longest distances. (I hope I did that correctly...)

2x2x2_two_color_graph.png


In this case, the "nonmixed" state is among those with smallest longest distance, though. And the "fully mixed" one is among those with largest longest distance, and is the one with largest average distance. Hrmpfh.
 
Last edited:
shadowslice e said:
How do you get 18/36 possible turns?
Click to expand...
18 is the 3x3x3 number: 6 faces (URFLDB) * 3 possible angles (R R' R2). For 5x5x5 there are two types of turns per face (R Rw). The 15^n computation is applicable to 3x3x3 only, because it's computing how many sequences you get if you don't use the same turn twice in a row (so each turn has 5 possible faces instead of 6, hence 5*3). Please understand the math before you use it :p
 
qqwref said:
18 is the 3x3x3 number: 6 faces (URFLDB) * 3 possible angles (R R' R2). For 5x5x5 there are two types of turns per face (R Rw). The 15^n computation is applicable to 3x3x3 only, because it's computing how many sequences you get if you don't use the same turn twice in a row (so each turn has 5 possible faces instead of 6, hence 5*3). Please understand the math before you use it :p
Click to expand...

Ok, I'll admit I made a few small (ok, huge) mistakes when making my calculations.
1) I forgot to factor in the different angles of turns (so multiply my answer by 3)
2) I miscounted what turns could be made for each face- 5 as opposed to 4 (I counted 5 as I thought w1, w2, w3, w4, w5 and discounted the opposite face which gave my calculation as 5+5+5 possible turns).
3) I didn't factor in discounting the double moves on the same face.

So I do understand the maths (although i made a couple of small, ok, huge, mistakes. But hey, what is peer review for? :-)) and didn't just copy the 3x3x3 calculation.

However, you also missed one thing- the calculation to perform the number of possible sequences would be 18x15^(n-1) as there would be no restrictions on what the first move would be.

So by extention could I not just redo the same calculation as 36x33^(n-1)?

If so then, we would need only 49 turns for the number of sequences to equal the number of possible permutations so thus I would reconclude that 60 is probably sufficient for a scramble.
 
Last edited:
shadowslice e said:
However, you also missed one thing- the calculation to perform the number of possible sequences would be 16x15^(n-1) as there would be no restrictions on what the first move would be.
Click to expand...
I didn't bring that up as I assumed you had also ignored it and were copying the 15^n from somewhere. The correct (but naive) computation is 18 * 15^(n-1) - or 36 * 33^(n-1) for 5x5x5. As I said, though, you have to take same-axis turns into account (you don't want to do R L R or R Rw R) and then it becomes a somewhat more complicated recursion, and the above numbers are just approximations.
 
qqwref said:
As I said, though, you have to take same-axis turns into account (you don't want to do R L R or R Rw R) and then it becomes a somewhat more complicated recursion, and the above numbers are just approximations.
Click to expand...

Well, we haven't even really done (as far as I'm aware) this calculation for 3x3x3 so, as far as I'm concerned until we crack 3x3x3 (other than by brute force) there's not much point trying to work out 5x5x5 (heck, we haven't (insofar as I have read) even done the brute force stuff for 4x4x4.)
 
shadowslice e said:
Well, we haven't even really done (as far as I'm aware) this calculation for 3x3x3 so, as far as I'm concerned until we crack 3x3x3 (other than by brute force) there's not much point trying to work out 5x5x5 (heck, we haven't (insofar as I have read) even done the brute force stuff for 4x4x4.)
Click to expand...

I've counted all 4x4x4 arrangements possible from the solved state through 32 moves. That's the first depth at which the unique move sequence count becomes greater than the total possible piece arrangemts, so it is naturally a lower bound for the 4x4x4 God's Number.

For the 5x5x5 I have the counts through move 50-something. I believe at 53 the number is bigger than the total combinations, so that would be the lower bound for the 5x5x5 if I am remembering correctly.
 
shadowslice e said:
Well, we haven't even really done (as far as I'm aware) this calculation for 3x3x3 so, as far as I'm concerned until we crack 3x3x3 (other than by brute force) there's not much point trying to work out 5x5x5 (heck, we haven't (insofar as I have read) even done the brute force stuff for 4x4x4.)
Click to expand...
I'm not sure what you're trying to say here. Obviously we are not going to actually figure out God's Number - I think I said this already.

The kind of calculation you posted is something which there is a lot of knowledge about, so I don't want someone to see your back-of-the-envelope wrong numbers and think they are the best known. The idea has been done many times (not just recently, but several years ago) and do actually provide decent lower bounds - that is, by calculating the number of positions you can get to with each number of moves, you can declare that God's Number has to be at least some number. I don't remember the exact numbers that come out of it (and it's slightly different for each possible way of counting moves), but it has been done and is probably a pretty good estimate.
 
If I didn't make a mistake, here are lower bounds for OBTM for cubes from 2x2x2 to 17x17x17. That uses the usual counting of scrambles by syllables.

Code: 
 n  moves  factor
-----------------
 2     9     6.00
 3    18    13.35
 4    35    20.73
 5    52    28.12
 6    75    35.51
 7    99    42.91
 8   128    50.31
 9   158    57.70
10   193    65.10
11   229    72.50
12   270    79.90
13   312    87.30
14   359    94.69
15   406   102.09
16   458   109.49
17   511   116.89

The "factor" is the branching factor of the last step.

Code: 
from math import factorial as f

def nCk(n, k):
    return f(n) // f(k) // f(n-k)

print(' n  moves  factor')
print('-----------------')
for n in range(2, 18):

    # Compute the number of states
    states = (24 * f(12) * 2**10)**(n%2) * f(7) * 3**6 * f(24)**((n**2-2*n)//4) // f(4)**(6*((n-2)**2//4))

    # Compute the number of scrambles, scrambles[m] := number of scrambles with m moves
    scrambles = [1]
    while sum(scrambles) < states:
        moves = len(scrambles)
        scrambles += sum((2 + (k == moves)) * nCk(n-1, k) * 3**k * scrambles[-k]
                         for k in range(1, min(n, moves+1))),

    print('%2d  %4d  %7.2f' % (n, moves, scrambles[-1] / scrambles[-2]))
The states-formula is [post=618528]from Chris[/post].
 
Last edited:
qqwref said:
I'm not sure what you're trying to say here. Obviously we are not going to actually figure out God's Number - I think I said this already.
Click to expand...
I'm saying that no one has ever written a paper based on mathematical concepts (such as vectors, group theory etc) that proves conclusively god's number for 3x3x3 is 20. The only reason we know that it is 20 is because we just crunched through every possible cube state and found a 20 move solution for all of them.

qqwref said:
The kind of calculation you posted is something which there is a lot of knowledge about, so I don't want someone to see your back-of-the-envelope wrong numbers and think they are the best known.
Click to expand...

I never claimed that it was the best we had- I was merely answering the question posed at the start of the thread- how many moves do we have to make before the total number of sequences of moves is greater than the number of possible permutations for a 5x5x5? (This was why it was stated that we established the lower bound for 3x3x3 as 18 and 4x4x4 as 32)
 
shadowslice e said:
no one has ever written a paper based on mathematical concepts (such as vectors, group theory etc) that proves conclusively god's number for 3x3x3 is 20. The only reason we know that it is 20 is because we just crunched through every possible cube state and found a 20 move solution for all of them.
Click to expand...

Here's a paper: http://tomas.rokicki.com/rubik20.pdf

And quite a bit of mathematical concepts went into it, especially group theory. Given that you recently didn't even know what commutators are, I suspect that you don't even understand the math that you just downplayed.
 
Stefan said:
Here's a paper: http://tomas.rokicki.com/rubik20.pdf

And quite a bit of mathematical concepts went into it, especially group theory. Given that you recently didn't even know what commutators are, I suspect that you don't even understand the math that you just downplayed.
Click to expand...

Did it sound like I was downplaying the maths? I definately didn't mean to. I know that a huge amount of effort and maths was placed into finding god's number but my point was that they still did have to crunch some numbers eventually- no matter all the amazing maths and insight they put into reducing and partitioning the cube space and number of cosets/subgroups they had to solve.

While I in no way mean to downplay what they did (I consider it to be one hell of an achievement), my point is that there is no purely mathematical paper that proves god's number without having to crunch through a few (albeit greatly reduced) cube states eventually (and, to be honest, I'm not entirely convinced this is possible and what these people achieved is likely the best we might ever had)

Thanks for the paper by the way, I was wondering where the 20-move proof was! :-)
 
Stefan said:
That's already called diameter. And I think "God's number" already is defined as the maximum number of moves needed to "solve" (to a specific "solved state").

Here's another puzzle, one with different average distances and different longest distances. (I hope I did that correctly...)

In this case, the "nonmixed" state is among those with smallest longest distance, though. And the "fully mixed" one is among those with largest longest distance, and is the one with largest average distance. Hrmpfh.
Click to expand...

A stickerless Square-1 is something similar.

http://www.jaapsch.net/puzzles/images/square1/shapes.gif

Although this graph is not the full graph, I think here the average distances and the longest distances also differ.
 
Stefan said:
If I didn't make a mistake, here are lower bounds for OBTM and SSTM for cubes from 2x2x2 to 17x17x17. That uses the usual counting of scrambles by syllables.

Code: 
 n  moves  factor
-----------------
 2     9     6.00
 3    18    13.35
 4    35    20.73
Click to expand...

This is OBTM, for SSTM the bounds are smaller, see http://cubezzz.dyndns.org/drupal/?q=node/view/236.
The asymptotic branching factor for OBTM is btw. 3/(1.5^(1/(-1+n))-1) which is more or less the factor of the last step.
 
Last edited:
You must log in or register to reply here.

Similar threads

B
God's number for the FTO
Replies
10
Views
812
BadDisplayName
B
iguana
What is God's number for a 3-gen scramble?
Replies
8
Views
645
Bruce MacKenzie
Bruce MacKenzie
A
4x4x4 OBTM (WTM) upper bound improved from 55 to 54
Replies
1
Views
435
SpeedCubingLord
SpeedCubingLord
D
God's Number and Pieces Rubik's Cube
Replies
5
Views
646
Deleted member 27249
D
C
Man's number challenge
Replies
6
Views
1,041
CubingKid
C
Back
Top