What is the closest cube state that has never been seen before?

[Mastermind2368]

As we all know, the Rubik's Cube has 43 quintillion possible combinations. Even with over 450 million cubes existing in the world, it is mathematically impossible for every combination to have been seen by a human. And with realizing that there's so many possible cube states that we've never seen, it got me thinking - how many moves away is the closest Rubik's Cube combination that nobody has seen before?

If my question sounds clunky, think about it like this. There are 18 possible combinations which are only 1 move away from being solved, and because the number is so few, they've obviously all been achieved before. Similarly, there are only 243 possible combinations which are only 2 moves way from being solved, and they've all been seen before by someone. So what is the amount of moves needed to reach a state that has never been seen?

Of course, this is impossible to answer exactly, and I'm quite frankly not sure how to fully go about estimating. I would imagine you would first want to estimate the total number of combinations that have been seen overall, and then do some weighted probability stuff (based on the amount of total combinations per move away from the solved state) to take an educated guess. Even then, I think it would be hard to know with certainty.

 

[ruffleduck]

Assuming each cube contributes 1000 unique states (low-ball estimate), I would estimate 10 or 11 moves.

 

[Discomantis]

I mean, does this count?

 

[Discomantis]

To sum up that video: There has been a 13 move scramble generated officially before. A 12 move scramble has also been generated officially, but that was an E1 scramble.

 

[Bruce MacKenzie]

As we all know, the Rubik's Cube has 43 quintillion possible combinations. Even with over 450 million cubes existing in the world, it is mathematically impossible for every combination to have been seen by a human. And with realizing that there's so many possible cube states that we've never seen, it got me thinking - how many moves away is the closest Rubik's Cube combination that nobody has seen before?

If my question sounds clunky, think about it like this. There are 18 possible combinations which are only 1 move away from being solved, and because the number is so few, they've obviously all been achieved before. Similarly, there are only 243 possible combinations which are only 2 moves way from being solved, and they've all been seen before by someone. So what is the amount of moves needed to reach a state that has never been seen?

Of course, this is impossible to answer exactly, and I'm quite frankly not sure how to fully go about estimating. I would imagine you would first want to estimate the total number of combinations that have been seen overall, and then do some weighted probability stuff (based on the amount of total combinations per move away from the solved state) to take an educated guess. Even then, I think it would be hard to know with certainty.

I did a search of the posts on the old Domain of the Cube Forum and found a report of a god's algorithm calculation out to depth 15f. I don't know if anyone has done the calculation out to a greater depth. So as for "seeing" as a computer representation all cube states have been "seen" out to 15f.

 

[Herbert Kociemba]

For the God’s number proof we solved up to symmetry all positions up to 15 moves optimally (and confirmed the number of 15 moves positions) and solved all other positions within 20 moves. So as a computer representation essentially all cube states have been seen.

 

[Bruce MacKenzie]

For the God’s number proof we solved up to symmetry all positions up to 15 moves optimally (and confirmed the number of 15 moves positions) and solved all other positions within 20 moves. So as a computer representation essentially all cube states have been seen.

One can map the states of the cube to the integers 1 to 43,252,003,274,489,856,000. An integer in that range thus may be deemed a representation of a cube state. If one sets up a computer to count from 1 to 43,252,003,274,489,856,000, on completion the program would have represented all states of the cube. Say it takes a millisecond per integer, then the calculation would take 1.37 billion years of cpu time. Even if you allow symmetry reduction where a representation of a member of an equivalence class is deemed a representation of all members of the class the time for such a calculation is prohibitive.


So I don't understand how your program for finding the diameter of the cube group generated representations for all group elements. It doesn't seem possible.
​

ADDENDUM

The above greatly underestimates how fast a computer can count. I wrote a little test of this. Since one is limited to 64 bit integers the representation must be factored. Here the representation is factored into a corner cubie permutation index, an edge cubie permutation index, a corner cubie orientation index and an edge cubie orientation index.

After running through the outer loop ten times the routine estimates that it would take right at 1300 cpu years for the calculation to complete.

[/JUSTIFY] -(void)doodle: (NSString *)input { NSDate *date; NSUInteger ep,cp,eo,co; NSTimeInterval elapsed; @autoreleasepool { date = [NSDate date]; for( ep = 0 ; ep < 479001600 ; ep++ ) [COLOR=rgb(84, 172, 210)]// 12! edge permutations[/COLOR] { if( [self Abort] ) { [self reportDone]; return; } if(ep > 0) { elapsed = -[date timeIntervalSinceNow] * 479001600 / ep; elapsed /= 3600 * 24 * 365.25; [self report: [NSString stringWithFormat: @"\nEstimate %G Years", elapsed]]; } for( cp = 0 ; cp < 20160 ; cp++ ) [COLOR=rgb(84, 172, 210)]// 8! / 2 corner permutations of correct parity[/COLOR] { for( eo = 0 ; eo < 2048 ; eo++ ) [COLOR=rgb(84, 172, 210)] // 2 to the 11th flip arrangements[/COLOR] { for( co = 0 ; co < 2187 ; co++ ) /[COLOR=rgb(84, 172, 210)]/ 3 to the 7th twist arrangements[/COLOR] { // [COLOR=rgb(84, 172, 210)]ep cp eo and co together specify a cube state[/COLOR] } } } } [self reportDone]; } } [JUSTIFY]

Estimate 1309.66 Years​

 

[Herbert Kociemba]

There are 2217093120 cosets of the subgroup H which has order 19508428800. By symmetry reduction we had to solve “only” 55882296 of these cosets. Solving all positions of a coset with <= 20 moves took about 20 s which is 1 000 000 000 positions/s. This performance was obviously the most important and critical part of our proof which reduced the time to solve all possible cube states to about 34 years.

 

[Herbert Kociemba]

or much less if you use many machines in parallel.

 

[Bruce MacKenzie]

There are 2217093120 cosets of the subgroup H which has order 19508428800. By symmetry reduction we had to solve “only” 55882296 of these cosets. Solving all positions of a coset with <= 20 moves took about 20 s which is 1 000 000 000 positions/s. This performance was obviously the most important and critical part of our proof which reduced the time to solve all possible cube states to about 34 years.

Perhaps I misunderstood, but it was my impression that not all cosets were actually solved. Say one has a coset S which has been determined to have a maximum depth of 19. One can define a daughter coset by multiplying all members of the coset by a face turn:

t • <S> = S2
<S> • t = S3

These daughter cosets have maximum depth ≤ 20. So this gives one as many as 36 cosets which one doesn't have to solve. You know that you're not going to find a depth > 20 element by solving these cosets. I thought that this logic was used to reduce the number of cosets actually solved.

 

[Isaiah Scott]

This is hurting my brain reading all of this............

 

[Herbert Kociemba]

Perhaps I misunderstood, but it was my impression that not all cosets were actually solved.

No, all cosets were solved. Not optimally of course, else we would know for example the exact number of 20 move positions. The coset solver takes an arbitrary position X from the coset. Then essentially we generate all positions of H which can be reached from this position X by at most 15 phase 1 moves (so we generate all optimal and suboptimal phase 1 solutions of X) and an appendix of at most 5 phase 2 moves. There is a one to one correspondence between these H- positions reached from X and positions of the coset which get completely solved by these moves. Only few positions of the coset cannot be solved in this 15 - 5 way. These are dealt individually by the two phase algorithm. Phase 1 will take at least 16 moves for these rare positions.

 

[Herbert Kociemba]

Phase 1 will take at least 16 moves for these rare positions.

If you try to explain something in a few sentences some interesting details get lost. So for example if you really would need 16 moves in phase 1 for the remaining positions 20 s to solve the whole coset would not work. But there are 3 different spatial orientations of a cube position and also the inverse position of these which have all the same distance to the solved state but usually different phase 1 lengths. So most of the time one of these 6 equivalent positions is easily solved with short phase 1. cube20.org gives an example of a really hard position where all 6 alternatives have a long phase 1.

 

[Herbert Kociemba]

Estimate 1309.66 Years

Without symmetry reduction which means that indeed all 4.3*10^19 possible cube states get solved in 20 moves by the coset solver our program would need about 1440 years. So counting the positions is not essentially faster than solving the positions. The hardware we refer to is a Nehalem X3460, 2.8 GHz using 4 cores.

 

[Bruce MacKenzie]

Without symmetry reduction which means that indeed all 4.3*10^19 possible cube states get solved in 20 moves by the coset solver our program would need about 1440 years. So counting the positions is not essentially faster than solving the positions. The hardware we refer to is a Nehalem X3460, 2.8 GHz using 4 cores.

Remarkable. Does that include the time needed to calculate the depth 15 optimal database? How many CPU years did that take?

 

[Herbert Kociemba]

Remarkable. Does that include the time needed to calculate the depth 15 optimal database? How many CPU years did that take?

For each coset with size 8!8!4!/2 it takes on the hardware described above on average 1.9 s for the phase 1 computation out to depth 15, 16 s for appending the 5 H moves and 1 s for dealing individually with the remaining positions . This is about 10^9 positions/s.

 

[Mastermind2368]

When posting this, I was originally just referring to physical representations of different combinations. Still, very interesting where this conversation ended up going.