3x3x3 explored out to 12 in FTM

[rokicki]

I just finished exploring the 3x3x3 out to 12 face turns. Here are the statistics, first for positions with exactly that distance:

 d  mod M + inv        mod M      positions
-- ------------ ------------ --------------
 0            1            1              1
 1            2            2             18
 2            8            9            243
 3           48           75           3240
 4          509          934          43239
 5         6198        12077         574908
 6        80178       159131        7618438
 7      1053077      2101575      100803036
 8     13890036     27762103     1332343288
 9    183339529    366611212    17596479795
10   2419418798   4838564147   232248063316
11  31909900767  63818720716  3063288809012
12 420569653153 841134600018 40374425656248

Next for positions with a distance less than or equal to d:

 d  mod M + inv        mod M      positions
-- ------------ ------------ --------------
 0            1            1              1
 1            3            3             19
 2           11           12            262
 3           59           87           3502
 4          568         1021          46741
 5         6766        13098         621649
 6        86944       172229        8240087
 7      1140021      2273804      109043123
 8     15030057     30035907     1441386411
 9    198369586    396647119    19037866206
10   2617788384   5235211266   251285929522
11  34527689151  69053931982  3314574738534
12 455097342304 910188532000 43689000394782

I believe this is the first time these numbers have been computed.

 

[jcuber]

This doesn't count the 6 rotations, right? (based on the fact that 0 ftm = 1 position)

 

[Jebediah54]

Impressive, but what do "mod M + inv" and "mod M" mean?

 

[rokicki]

"mod M" means the count of representative sets from the cube rotation/mirror group M (24 rotations x 2 mirror images). "mod M + inv" means count of representative sets from the group M plus inversion (if position p is in the set, then so is position p'). The two of these together make the exploration problem about 96 times easier.

 

[AvGalen]

Yeah for numbers......but much more yeah for an explanation!

In other words: What does all of this mean (in English, not in math/cuboid please)

 

[rahulkadukar]

Seriously what are these numbers

 

[Stefan]

These tables tell us how many different cubes we can reach with a certain number of moves, starting from the solved cube. You maybe think you can reach 18 different cubes with one turn - choose from 6 sides and between 3 degrees (90/180/270), and 6*3=18.

But is the cube you get with R U2 really different from the one you get with F L2? Well, they sure look different at first sight, but you really did the same thing twice, just from different angles. A clockwise quarter turn on one side, then a double turn on an adjacent side. So the question is, how many really different cubes do we get? For that you must specify what exactly you mean with different. Thinking positively, we instead specify what we consider equivalent. And what we consider equivalent will only be counted once.

That's where the symmetries come into play. The M symmetry considers equivalent what just differs by whole cube rotation and mirroring, for example R U2 is considered equivalent to F' L2. The inv symmetry considers equivalent what just differs by inversing, for example L U2 is considered equivalent to U2 L'. Take both symmetries together and you also consider L U2 equivalent to let's say F2 R.

Example:

d  mod M + inv
-- ------------
 0            1
 1            2
 [B]2[/B]            [B]8[/B]

This tells you that considering M and inv, after 2 moves there are 8 different possibilities:

Cubes equivalent to R L
Cubes equivalent to R L'
Cubes equivalent to R L2
Cubes equivalent to R2 L2
Cubes equivalent to R U
Cubes equivalent to R U'
Cubes equivalent to R U2
Cubes equivalent to R2 U2

 

[Die_d00pel_Null]

uhm does that mean that for d>=24 mod M+inv will be bigger than 43 quintrillonen which would prove the upper move bound of 3x3x3 being 24 moves in FTM?

 

[Stefan]

uhm does that mean that for d>=24 mod M+inv will be bigger than 43 quintrillonen which would prove the upper move bound of 3x3x3 being 24 moves in FTM?

No and no.

 

[Die_d00pel_Null]

hm okay and why?

 

[Stefan]

Well why should it?

 

[Die_d00pel_Null]

hm yes I just found out that the upper move bound is 22 moves and that the superflip just requires 20 moves to be solved. This brings me to the much more interesting question what kind of scramble can only be solved in 22 moves?
So if there are 43 quintrillionen different positions on the 3x3 rubiks cube and all of these positions can be solved in 22 turns then mod M + inv should be 43 quintrillionen if d is 22. Because you can reach all positions in 22 moves

 

[mrCage]

I just finished exploring the 3x3x3 out to 12 face turns. Here are the statistics, first for positions with exactly that distance:

 d  mod M + inv        mod M      positions
-- ------------ ------------ --------------
 0            1            1              1
 1            2            2             18
 2            8            9            243
 3           48           75           3240
 4          509          934          43239
 5         6198        12077         574908
 6        80178       159131        7618438
 7      1053077      2101575      100803036
 8     13890036     27762103     1332343288
 9    183339529    366611212    17596479795
10   2419418798   4838564147   232248063316
11  31909900767  63818720716  3063288809012
12 420569653153 841134600018 40374425656248

Next for positions with a distance less than or equal to d:

 d  mod M + inv        mod M      positions
-- ------------ ------------ --------------
 0            1            1              1
 1            3            3             19
 2           11           12            262
 3           59           87           3502
 4          568         1021          46741
 5         6766        13098         621649
 6        86944       172229        8240087
 7      1140021      2273804      109043123
 8     15030057     30035907     1441386411
 9    198369586    396647119    19037866206
10   2617788384   5235211266   251285929522
11  34527689151  69053931982  3314574738534
12 455097342304 910188532000 43689000394782

I believe this is the first time these numbers have been computed.

Does this consider the supergroup?? Inther words does it consider sequences with same effect on movable cubies but different orientation of centers to be the same ??

Ie would U2 L R' F2 L' R and (R2 U2 R2 F2)*2 be considered same??

-Per

 

[Stefan]

1. Stats for d<=12 don't really tell much about d>=24.
2. It is not known whether 22 is the least upper bound.
3. No position requiring more than 20 moves to solve is known.
4. There are slightly more than 43 quintillion (not "quintrillionen") positions.
5. mod M + inv there are only 450,541,810,590,509,978 positions (knock yourself out)

 

[Die_d00pel_Null]

hm maybe I should just try to get faster and stop thinking about what I'm doing

okay thanks but doesn't this page http://cubezzz.homelinux.org/drupal/?q=node/view/121 prove that "every position of Rubik's cube can be solved in 22 or fewer face turns." ?!

 

[Stefan]

okay thanks but doesn't this page http://cubezzz.homelinux.org/drupal/?q=node/view/121 prove that "every position of Rubik's cube can be solved in 22 or fewer face turns." ?!

Yeah. What's your point?

 

[Die_d00pel_Null]

It contradicts your point 2 and point 3 in your previous post.

 

[AvGalen]

It contradicts your point 2 and point 3 in your previous post.

No it doesn't.

Consider this statement:
Every child's allowance on the planet can be paid if the parents have 1 million dollar

Now both of these statements are true:
"2". It is not known whether 1 million dollar is the least amount of money parents would need
"3". No allowance requiring more than 20000 dollar to pay is known.

So basically:
* It has been (mathematically) proven that every cube can be solved in 22 moves or less.
* It has been (empirically) proven that a cube exists that needs 20 moves to solve.
* No cubes are known that require 21 or 22 moves, but they might exist

 

[Stefan]

3. No position requiring more than 20 moves to solve is known.

Actually, let me strengthen that:
3. No position requiring more than 20 moves to solve is known to exist.

 

[Rune]

These tables tell us how many different cubes we can reach with a certain number of moves, starting from the solved cube. You maybe think you can reach 18 different cubes with one turn - choose from 6 sides and between 3 degrees (90/180/270), and 6*3=18.

But is the cube you get with R U2 really different from the one you get with F L2? Well, they sure look different at first sight, but you really did the same thing twice, just from different angles. A clockwise quarter turn on one side, then a double turn on an adjacent side. So the question is, how many really different cubes do we get? For that you must specify what exactly you mean with different. Thinking positively, we instead specify what we consider equivalent. And what we consider equivalent will only be counted once.

That's where the symmetries come into play. The M symmetry considers equivalent what just differs by whole cube rotation and mirroring, for example R U2 is considered equivalent to F' L2. The inv symmetry considers equivalent what just differs by inversing, for example L U2 is considered equivalent to U2 L'. Take both symmetries together and you also consider L U2 equivalent to let's say F2 R.

Example:

d  mod M + inv
-- ------------
 0            1
 1            2
 [B]2[/B]            [B]8[/B]

This tells you that considering M and inv, after 2 moves there are 8 different possibilities:

Cubes equivalent to R L
Cubes equivalent to R L'
Cubes equivalent to R L2
Cubes equivalent to R2 L2
Cubes equivalent to R U
Cubes equivalent to R U'
Cubes equivalent to R U2
Cubes equivalent to R2 U2

A silly question? If you only consider M, what is the 9th possibility?