• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

God's Second Number?

elrog

Member
Joined
Jan 31, 2013
Messages
518
Location
U.S.A.
YouTube
Visit Channel
I posted this post a while back in this thread. It is the last post on page 7 if you have 10 posts per page.
I would like to clarify something in your post. You said that X moves have the same chance to give a random state, but some states are more likely to occur than others due to symmetries. On a supercube, every state has equal probability. I think what you were meaning though is that X moves and Y moves both have the same chance to come up with the same state.

Lets say you start at any particular random state on the cube. If you apply exactly 20 moves to the cube, there may be cases that are still unreachable. Take a state that is 19 moves optimally from the state you started at. That state is only reachable if it is solvable in 20 moves as well as the optimal 19 moves. I am fairly certain that there are 19 move optimal solutions that cannot be solved in exactly 20 moves because there are also 5 move solutions which cannot be solved in 6 moves.

It is true that the probability would eventually be the same, but to define the point, you would have to find a number big enough that every state can be solved in exactly that many moves. There may also be a few numbers of moves above this number of moves which cannot cover every position, but it seems that eventually you would reach a point where any number of moves above this number, whatever it may be, would be able to cover every position. I cannot be to sure though as prime numbers would seem the same way, but they really only become further and further apart.


Oh, and to answer the original question disregarding the point that the chances are so small, I have not and may not ever attend a competition, and that the scramble would surely be thrown out, I would solve the cube in 1 move STM if possible and give up if it wasn't possible.

I thought about this a little more and realized something. If any position of the cube can be reached in exactly 35 (this is just an example) moves (HTM because that's how God's Number was found), then you can reach any position starting at any position, and any position can be reached with any number of moves above 35 moves because you can just apply any number of moves to the starting state and apply a different set of 35 moves.

After realizing this, I was wondering just what that number may be. To get an idea I took a look at the superflip (a well known position that requires 20 moves optimally HTM). An optimal solution for the superflip is U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2. Because of the symmetry of this position, any move you make makes the position closer to solved.

If you do a single move to the superflip position, you make a 19 move solution possible, but there is also a 20 move position possible as well because you can cancel at the beginning or end of the superflip alg because it has a 90 degree turn on one end and a 180 degree turn on the other. Doing any two moves on adjacent sides also can cancel out to give a 20 move solution. If you do any two moves on opposite sides, you will not be able to cancel both of them out and no 20 move solution is possible.

This would verify that 21 moves is the lower bound as long as there is no other optimal solution for the superflip that is not an inverse or mirror of the given algorithm (I don't think there is). Going by this logic, I could go further but I would likely run into other 20 move optimal positions.
 

Robert-Y

Member
Joined
Jan 21, 2009
Messages
3,289
Location
England
WCA
2009YAUR01
YouTube
Visit Channel
Are you asking what is the maximum distance between any two states of the Rubik's Cube in HTM?

It's rather unclear to me what you asking for (if anything)... :S
 
Joined
Mar 18, 2014
Messages
687
Location
in d middle of angleland
WCA
2009WHIT01
YouTube
Visit Channel
Are you asking what is the maximum distance between any two states of the Rubik's Cube in HTM?

It's rather unclear to me what you asking for (if anything)... :S

i wasnt sure if hes asking for that (which is 20) or the smallest N where every state has at least 1 solution of length N (i wouldnt be surprised if that is also 20)
 

elrog

Member
Joined
Jan 31, 2013
Messages
518
Location
U.S.A.
YouTube
Visit Channel
the smallest N where every state has at least 1 solution of length N

That is what I am looking for in HTM. I think it is over 20 by a little bit. If it was 20, you are saying every 19 move strong position is also solvable in exactly 20 moves. It is obvious that you cannot solve every 5 move strong position in 6 moves exactly.

Edit:
I have found multiple 20 move solutions to the superflip, so I don't think it is a good candidate for extended searches.

I have moved on to checking this scramble: F U' F2 D' B U R' F' L D' R' U' L U B' D2 R' F U2 D2

I have found 21 and 22 move solutions to this scramble, but no other 20 move solutions yet. If I can confirm there are no other 20 move solutions, I can make 21 a lower bound.
 
Last edited:

porkynator

Member
Joined
Oct 27, 2010
Messages
1,322
Location
Belluno, Italy
WCA
2011TRON02
YouTube
Visit Channel
Let's say you have an N-moves solution for a scramble. Let's suppose its last move is U.
You want an (N+1)-moves solution? Change the last move to U2 U'. You want an (N+2)-moves solution? Add R2 R2 at the end. And so on.
Conclusion: you can solve every position in exactly N moves for each N >= 20.
 

elrog

Member
Joined
Jan 31, 2013
Messages
518
Location
U.S.A.
YouTube
Visit Channel
.. I never dreamed I would have to specify that I don't want to do multiple turns of the same layer in a row...

@ mark - If there is only one 20 move solution, it will be possible to slightly change the scramble to a new one so that the new solution (which includes the old solution with a slight change) is longer. There will undoubtedly be a completely unique shorter solution to the new scramble too because God's number is 20. If there are many 20 move solution to a case, you will have to change the scramble so much (to make a new, longer solution for each old solution) that you will end up introducing a completely unique 20 move scramble.

I hope that made sense.
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
I don't think that makes sense, no. You will have to formalize it or find a 19f* position which has no 20-move solutions. If what you're saying is true it should be easy to find ;)

I think for this problem it is definitely important to specify what you mean by move sequence. The distinction does not matter for God's Algorithm since it is not affected by suboptimal versions of move sequences. I assume you are talking about a canonical move sequence (what we used in scramblers), i.e. a move sequence which cannot be shortened by repeated application of the operations (a) combine two adjacent turns of the same face, and (b) swap two adjacent turns on the same axis.

If every position does turn out to have a 20 move solution, I propose a second question: what is the largest N for which there is an Nf* position with no (N+1)-move canonical solution?
 
Last edited:

mark49152

Premium Member
Joined
Oct 29, 2012
Messages
4,719
Location
UK
WCA
2015RIVE05
YouTube
Visit Channel
@elrog: Sorry, I don't follow your logic at all, even after re-reading several times. It's a very interesting question though.

If a 20f* position really has only one optimal solution, that means that 17 of its adjacent positions are also 20f* (the other one would be 19f* of course). Statistically that seems very, very unlikely. I wonder if it would be meaningful to predict the probability from the distribution tables for optimal solutions? My intuition makes me suspect that 20f* positions are mostly little individual islands in a sea of <=19f* positions.

As qqwref said, I think that to prove that 20 isn't the answer, you have to find a position with no 20f solution. I'm not sure why that position would have to be 19f* but let's assume it is. You'd effectively have to prove that it has no 19f* neighbours, and none of its 18f* neighbours have 19f solutions. And so on. I have no idea how that could be done but it sounds difficult and impractical.

Alternatively you could prove that for a certain N, any N-move canonical sequence can be replaced with an (N+1)-move canonical sequence. Obviously the lower the N the easier the search or proof, but if you could prove it for any N<=19 then you're done and 20 is your answer. I have no idea how hard that would be. Perhaps it could be simplified by reducing the subgroup, e.g. applying to non-canonical sequence of quarter turns?
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
I ran some CubeExplorer while at work and luckily came up with this position: B' R D' B2 L' F2 U' B2 D' F L B2 R D2 L' (15f*). There are 17f solutions (at least three of them) but no 16f solutions.

Note that this does not by itself prove anything about God's Second Number :p
 

mark49152

Premium Member
Joined
Oct 29, 2012
Messages
4,719
Location
UK
WCA
2015RIVE05
YouTube
Visit Channel
I ran some CubeExplorer while at work and luckily came up with this position: B' R D' B2 L' F2 U' B2 D' F L B2 R D2 L' (15f*). There are 17f solutions (at least three of them) but no 16f solutions.

Note that this does not by itself prove anything about God's Second Number :p
Oh well, that kills my second idea :(. I wonder if that property can be determined by analysis of a sequence? For example, would a sequence have to have certain characteristics in order to not be replaceable in whole or part by a different sequence one move longer?
 

elrog

Member
Joined
Jan 31, 2013
Messages
518
Location
U.S.A.
YouTube
Visit Channel
I know that I have to find a position with no 20 move solution in HTM to prove that this number is not 20. What I described is just how I plan on finding one after my cube explorer search finishes. I have set it up with the "hardest" case and 1 piece greyed out so it will show all solutions. It as at 17 moves after over 12 hours. I will have to wait until it gets to 21 to have the information I want.

I have been looking through 20 move positions that I found here.

So far, comparing the seemingly harder scrambles to the easier ones, the harder scrambles seem to be lower move counts in QTM. Is there any position which takes 20 moves both HTM and QTM?
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
I know that I have to find a position with no 20 move solution in HTM to prove that this number is not 20. What I described is just how I plan on finding one after my cube explorer search finishes. I have set it up with the "hardest" case and 1 piece greyed out so it will show all solutions. It as at 17 moves after over 12 hours. I will have to wait until it gets to 21 to have the information I want.
Bad news, each extra move takes something like 15 times as long. You can expect to wait months or years to get up to 21. Maybe try the Huge Optimal Solver or ACube instead?

So far, comparing the seemingly harder scrambles to the easier ones, the harder scrambles seem to be lower move counts in QTM. Is there any position which takes 20 moves both HTM and QTM?
I don't think people know much about QTM (not even a good guess at God's Number). I know of a 20h/26q but not a 20h/20q, although I'm sure there is one.
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
Is there any position which takes 20 moves both HTM and QTM?

Superfliptwist. Source: http://www.cflmath.com/~reid/Rubik/h_symmetric.html
U R F' B U' D' F U' D F L F' L' U R D F U R L (20q*, 20f*)

There is also this post that gives some positions that are the same distance in both FTM and QTM.
http://cubezzz.dyndns.org/drupal/?q=node/view/174

EDIT: And by the way, God's number in QTM has been narrowed down to either 26 or 27, although it's almost certain to be 26.
 
Last edited:

EMI

Member
Joined
Apr 23, 2011
Messages
848
Location
Germany
WCA
2011RHEI01
YouTube
Visit Channel
Last edited:

elrog

Member
Joined
Jan 31, 2013
Messages
518
Location
U.S.A.
YouTube
Visit Channel
Thank you Bruce.

I am currently not at home and won't be for a few days. I did leave cube explorer running when I left though. I was trying to see what all of the symmetry options did. I left it trying to find an identity with 6 colors selected. All I know is that about 8 hours in, it had no progress.

Does the number of colors mean there is at least that many colors on each side? So far it seems this way.
 
Top