• 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!

3x3x3 explored out to 12 in FTM

rokicki

Member
Joined
Oct 31, 2008
Messages
301
I just finished exploring the 3x3x3 out to 12 face turns. Here are the statistics, first for positions with exactly that distance:
Code:
 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:
Code:
 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.
 

rokicki

Member
Joined
Oct 31, 2008
Messages
301
"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.
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
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:

Code:
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
 
Joined
Feb 28, 2009
Messages
20
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?
 
Joined
Feb 28, 2009
Messages
20
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

Member
Joined
Jun 17, 2006
Messages
655
I just finished exploring the 3x3x3 out to 12 face turns. Here are the statistics, first for positions with exactly that distance:
Code:
 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:
Code:
 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
 
Last edited:

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
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)
 
Last edited:

AvGalen

Premium Member
Joined
Jul 6, 2006
Messages
6,857
Location
Rotterdam (actually Capelle aan den IJssel), the N
WCA
2006GALE01
YouTube
Visit Channel
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
 

Rune

Premium Member
Joined
May 11, 2006
Messages
277
WCA
2003WESS01
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:

Code:
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?
 
Top