# 3x3x3 explored out to 12 in FTM



## rokicki (Jun 24, 2009)

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 (Jun 24, 2009)

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


----------



## Jebediah54 (Jun 24, 2009)

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


----------



## rokicki (Jun 24, 2009)

"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 (Jun 24, 2009)

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 (Jun 24, 2009)

Seriously what are these numbers


----------



## Stefan (Jun 24, 2009)

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 (Jul 14, 2009)

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 (Jul 14, 2009)

Die_d00pel_Null said:


> 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 (Jul 14, 2009)

hm okay and why?


----------



## Stefan (Jul 14, 2009)

Well why should it?


----------



## Die_d00pel_Null (Jul 14, 2009)

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 (Jul 14, 2009)

rokicki said:


> 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
> ...


 
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 (Jul 14, 2009)

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 (Jul 14, 2009)

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 (Jul 14, 2009)

Die_d00pel_Null said:


> 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 (Jul 14, 2009)

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


----------



## AvGalen (Jul 14, 2009)

Die_d00pel_Null said:


> 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 (Jul 14, 2009)

StefanPochmann said:


> 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 (Jul 14, 2009)

StefanPochmann said:


> 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.
> 
> ...



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


----------



## Johannes91 (Jul 14, 2009)

uweren2000 said:


> StefanPochmann said:
> 
> 
> > This tells you that considering M and inv, after *2* moves there are *8* different possibilities:
> ...



*R2 U*


----------



## Lucas Garron (Jul 14, 2009)

uweren2000 said:


> StefanPochmann said:
> 
> 
> > 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.
> ...


*R2 U*, I think.


----------



## Stefan (Jul 14, 2009)

Yes, cubes equivalent to *R2 U*. Considering inv in addition to M, it's equivalent to R U2.

You might wonder why not *R2 L*. That's because it's equivalent to R L2 already considering M alone.


----------



## Herbert Kociemba (Jul 14, 2009)

uweren2000 said:


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



For example R2 U.

Edit: Did not see that Lucas and Stefan already gave the answer


----------



## Rune (Jul 14, 2009)

Herbert Kociemba said:


> uweren2000 said:
> 
> 
> > A silly question? If you only consider M, what is the 9th possibility?
> ...



For example?


----------



## Herbert Kociemba (Jul 15, 2009)

uweren2000 said:


> Herbert Kociemba said:
> 
> 
> > uweren2000 said:
> ...



Yes, for example. Because you also may take R2 U' or U2 R etc. for the 9th possibility.


----------

