# 2x2x2 Scramble Math Question



## reThinking the Cube (Feb 23, 2010)

Here is the well known distribution table for min#of moves to solve 2x2x2. 

n f
0
0 1
1 9
2  54
3 321
4 1847
5 9992
6 50136
7 227536
8 870072
9 1887748
10 623800
11 2644
12 0
13 0
14 0 
Total 3674160

How many of these 3,674,160 positions would yield a scrambled cube with no more than one correctly placed piece? (simultaneously - nothing else solved except for 1 arbitrary reference corner).

+10 Bonus: a table (min#of moves to solve) like the one above for just those positions.
.


----------



## qqwref (Feb 23, 2010)

I expect Lucas to come up with a Mathematica one-liner in an hour or two, so I'm not going to try to calculate this myself. It's an interesting problem, though.


----------



## ianini (Feb 23, 2010)

qqwref said:


> I expect Lucas to come up with a Mathematica one-liner in an hour or two, so I'm not going to try to calculate this myself. It's an interesting problem, though.



I actually thought you were going to be the one to answer this question.


----------



## DavidWoner (Feb 23, 2010)

Shortest qtm is U F2 R I believe


----------



## TomZ (Feb 23, 2010)

The distribution of positions on the 2x2x2 that have at least 2/8 pieces solved is:


```
#0: 1 position
#1: 9 positions
#2: 54 positions
#3: 165 positions
#4: 827 positions
#5: 3740 positions
#6: 17478 positions
#7: 69586 positions
#8: 250422 positions
#9: 520180 positions
#10: 177808 positions
#11: 1240 positions
#12: 0 positions
```

That means that 1041510/3674160 or around 28% of the positions of the 2x2x2 have at least two pieces solved.


----------



## cmhardw (Feb 23, 2010)

TomZ said:


> That means that 1041510/3674160 or around 28% of the positions of the 2x2x2 have at least two pieces solved.



I just wanted to post that I don't agree with this calculation for how many positions there are with at least two solved pieces. If you count the number of positions where exactly 1 corner is solved, essentially a derangement of the other pieces after the 1st corner is rotated to be solved, you get:

7!*3^6 - (7 C 1)*6!*3^5 + (7 C 2)*5!*3^4 - (7 C 3)*4!*3^3 + (7 C 4)*3!*3^2 - (7 C 5)*2!*3^1 + 1

= 2632645

(Number of positions with exactly 1 solved piece) + (Number of positions with at least two solved pieces) = Total number of solved positions

Keep in mind that for a 2x2x2 the total number of positions is calculated by "solving" one corner as a reference point. Therefore:

2632645 + 1041510 = 3674155 /= 3674160

Where are the missing 5 positions? Was this a simple miscalculation? I will admit my ignorance in saying that I can't tell if the error is mine, or in that table you posted.

*--edit--*
I think I found the error, and it was mine.

Derangements of the other 7 corners should be:
7!*3^6 - (7 C 1)*6!*3^5 + (7 C 2)*5!*3^4 - (7 C 3)*4!*3^3 + (7 C 4)*3!*3^2 - (7 C 5)*2!*3^1 + (7 C 6)*1!*3^0 - 1

= 2632650

And therefore:
2632650 + 1041510 = 3674160

And I agree with the calculation.

*-------------------*

Chris


----------



## qqwref (Feb 23, 2010)

I think calculations of this type would be disregarding positions in which two pieces (neither of which are the fixed piece) are solved relative to each other, though. I think the best way to do this would be to just exhaustively generate and provide an optimal length for each position satisfying this property.


----------



## reThinking the Cube (Feb 24, 2010)

qqwref said:


> I think calculations of this type would be disregarding positions in which two pieces (neither of which are the fixed piece) are solved relative to each other, though.



MG is correct. There are 8 possibilities (not just 1) that can be used for the solved reference piece. For ANY one of them, if another piece is found that is solved relative to that reference, then the position as a whole contains more than 1 solved piece by cube rotations alone. 
.


----------



## cuBerBruce (Feb 24, 2010)

reThinking the Cube said:


> qqwref said:
> 
> 
> > I think calculations of this type would be disregarding positions in which two pieces (neither of which are the fixed piece) are solved relative to each other, though.
> ...



I get the following distribution:


```
moves   n=1      n=2      n=3      n=4      n=5      n=6      n=8   totals   n >= 2

 0        0        0        0        0        0        0        1        1        1
 1        0        0        0        9        0        0        0        9        9
 2        0       54        0        0        0        0        0       54       54
 3       48      186        0       87        0        0        0      321      273
 4      264      956      528       99        0        0        0     1847     1583
 5     1092     6302     1944      654        0        0        0     9992     8900
 6     7092    35976     6408      660        0        0        0    50136    43044
 7    44904   151900    26592     3948      192        0        0   227536   182632
 8   186864   577424    99688     5328      768        0        0   870072   683208
 9   451728  1235424   186288    13524      784        0        0  1887748  1436020
10   151512   401360    62496     7932      384      116        0   623800   472288
11      240     1776      328      276        0       24        0     2644     2404
     ------  -------   ------    -----      ---      ---        -  -------  -------
     843744  2411358   384272    32517     2128      140        1  3674160  2830416

Edit: average number of moves added, per Stefan's request
     8.8199   8.7447   8.6894   8.6794   8.6391  10.1714   0.0000   8.7556   8.7364
```


----------



## Stefan (Feb 24, 2010)

Bruce, can you add average number of moves to each column?


----------



## reThinking the Cube (Feb 25, 2010)

cuBerBruce said:


> reThinking the Cube said:
> 
> 
> > qqwref said:
> ...



+10, and I owe you a case of your favorite Bruce! Very nice, I must have spent over an hour just looking/staring at this table. Pretending that all of the scrambles for 2x2x2 came from the bolded item above, I was wondering if it would be possible to reduce those, by rotations, reflections, inverses, and 1 face turn conjugations to get a bare bones minimum# of algs that would have to be learned to one-look solve just those 451,728 positions?


----------



## cuBerBruce (Feb 25, 2010)

reThinking the Cube said:


> +10, and I owe you a case of your favorite Bruce! Very nice, I must have spent over an hour just looking/staring at this table. Pretending that all of the scrambles for 2x2x2 came from the bolded item above, I was wondering if it would be possible to reduce those, by rotations, reflections, inverses, and 1 face turn conjugations to get a bare bones minimum# of algs that would have to be learned to one-look solve just those 451,728 positions?



There are a total of 40296 equivalence classes when reducing the 2x2x2 positions by symmetry and antisymmetry (that is, with cube rotations, reflections, and inverses). The case 451728 positions for n=1, distance=9 correspond to 4820 of these equivalence classes. I also calculated that the 1235424 positions for n=2 distance=9 correspond to 13353 of these equivalence classes. (I have not used conjugation by 1 turn ("face" turns???).)

I note that my "n" is the number of solved pieces including the piece used as a reference, and the reference is chosen that maximizes the number of solved pieces. So n=1 means that only the reference piece is considered solved regardless of which piece is chosen as the reference. n=2 means there is a choice of reference piece such that 1 other piece is solved with respect to it.


----------



## reThinking the Cube (Feb 27, 2010)

cuBerBruce said:


> There are a total of 40296 equivalence classes when reducing the 2x2x2 positions by symmetry and antisymmetry (that is, with cube rotations, reflections, and inverses). The case 451728 positions for n=1, distance=9 correspond to 4820 of these equivalence classes.



Bruce, can you include equivalence class numbers along with position counts? I am curious to see the equiv.#'s working backwards for moves=0,1,2,3,4..., 

Also, is it possible for you to determine how many of these can be solved with a 2-generator alg?


----------



## miniGOINGS (Feb 27, 2010)

reThinking the Cube said:


> Also, is it possible for you to determine how many of these can be solved with a 2-generator alg?



I 2-Gen alg would only work if 2 corners are solved next to each other, and corner permutation is correct, which I believe is 1/3. I would also be interested in this.


----------



## cuBerBruce (Feb 28, 2010)

reThinking the Cube said:


> cuBerBruce said:
> 
> 
> > There are a total of 40296 equivalence classes when reducing the 2x2x2 positions by symmetry and antisymmetry (that is, with cube rotations, reflections, and inverses). The case 451728 positions for n=1, distance=9 correspond to 4820 of these equivalence classes.
> ...



The table for symmetry/antisymmetry equivalence classes is:


```
moves  n=1     n=2     n=3     n=4     n=5     n=6     n=8
 0       0       0       0       0       0       0       1
 1       0       0       0       2       0       0       0
 2       0       4       0       0       0       0       0
 3       3       7       0       4       0       0       0
 4       7      24       7       3       0       0       0
 5      24      98      23      12       0       0       0
 6      93     434      72      13       0       0       0
 7     511    1710     293      59       3       0       0
 8    2002    6255    1073      71       9       0       0
 9    4820   13353    2038     187      12       0       0
10    1642    4501     726     129       9       6       0
11       3      36       8       7       0       2       0
```



miniGOINGS said:


> reThinking the Cube said:
> 
> 
> > Also, is it possible for you to determine how many of these can be solved with a 2-generator alg?
> ...



If 2 adjacent corners are correctly solved with respect to each other, there are 6! = 720 permutations for the last 6 pieces of which I believe 1/6 are solvable turning only the layers not containing the two solved pieces.

Some positions may have more than one pair of correctly solved corners. Which pair is chosen to be fixed may affect whether or not the position is solvable turning only the layers not containing the chosen pair.

(My phone & internet service has been out for about 49 hours so my responses may be sporadic until Verizon fixes my connection.)

EDIT:
2-gen information

First I simply calculated all the 2-gen positions. I give results for both <U,R> positions only (solved within <U,R>), and for all 2-gen positions when allowing any of the 12 choices for the two layers to be turned. I note that the total number of 2-gen solvable positions is a prime number (316699).


```
moves    <U,R>  all 2-gen

  0         1         1
  1         6         9
  2        18        54
  3        53       267
  4       148      1308
  5       400      4440
  6       910     10536
  7      1882     22008
  8      3276     38088
  9      4628     51124
 10      6198     65828
 11      6325     67104
 12      4352     46392
 13       941      9348
 14        22       192
        -----    ------
        29160    316699
```

Next, I give the results (number of 2-gen solvable positions) with respect to the number of solved pieces and moves required to solve (3-gen or 2-gen).


```
Number of 2-gen solvable positions with respect to 3-gen distance and number of solved pieces.

moves   n=1     n=2     n=3     n=4     n=5     n=6     n=8       totals
(3-gen)									
  0       0       0       0       0       0       0       1            1
  1       0       0       0       9       0       0       0            9
  2       0      54       0       0       0       0       0           54
  3       0     180       0      87       0       0       0          267
  4       0     684     528      96       0       0       0         1308
  5       0    2568    1296     624       0       0       0         4488
  6       0    9240    2352     528       0       0       0        12120
  7       0   24288    7104    2820       0       0       0        34212
  8       0   62888   26472    1824      48       0       0        91232
  9       0  100528   35784    3996      48       0       0       140356
 10       0   22416    8208    1680      16      56       0        32376
 11       0     144      96      24       0      12       0          276
          -  ------   -----   -----     ---      --       -       ------
totals    0  222990   81840   11688     112      68       1       316699


Number of 2-gen solvable positions with respect to 2-gen distance and number of solved pieces.
      
moves   n=1     n=2     n=3     n=4     n=5     n=6     n=8       totals
(2-gen)									
  0       0       0       0       0       0       0       1            1
  1       0       0       0       9       0       0       0            9
  2       0      54       0       0       0       0       0           54
  3       0     180       0      87       0       0       0          267
  4       0     684     528      96       0       0       0         1308
  5       0    2520    1296     624       0       0       0         4440
  6       0    8232    1968     336       0       0       0        10536
  7       0   15432    4944    1632       0       0       0        22008
  8       0   25440   12024     576      48       0       0        38088
  9       0   36784   12624    1668      48       0       0        51124
 10       0   45548   18720    1512      16      32       0        65828
 11       0   48096   16584    2388       0      36       0        67104
 12       0   33456   10872    2064       0       0       0        46392
 13       0    6468    2184     696       0       0       0         9348
 14       0      96      96       0       0       0       0          192
          -  ------   -----   -----     ---      --       -       ------
          0  222990   81840   11688     112      68       1       316699
```


----------



## reThinking the Cube (Mar 3, 2010)

Nice work! These tables are very interesting. 

Bruce, could you generate for the #of moves away, all 3674160 are from any n>=4 position? That would reveal the potential for human transitions into the easier known cases.



cuBerBruce said:


> The table for symmetry/antisymmetry equivalence classes is:
> 
> 
> ```
> ...



Any chance of getting diagrams, or specific cycle descriptions for those n=4,5,6 above?
.


----------



## cuBerBruce (Mar 4, 2010)

reThinking the Cube said:


> Nice work! These tables are very interesting.
> 
> Bruce, could you generate for the #of moves away, all 3674160 are from any n>=4 position? That would reveal the potential for human transitions into the easier known cases.
> 
> ...



OK, I have created a file with all the distinct cases (with respect to symmetry and antisymmetry) with 4 or more pieces solved (excluding the trivial case of all 8 solved).

I provide the cycle structure of one representative for each case. Unfortunately, the choice of representative is rather arbitrary. Cycles can be of one of two types: "oriented" cycles and "misoriented" cycles. For "oriented" cycles, the cycle length is equal to the number of cubies in the cycle. For "misoriented" cycles, the cycle length is 3 times the number of cubies in the cycle. For "misoriented" cycles, the full cycle is not included - only up to the point where the initial cubie is repeated (but with different "orientation"). An ellipsis ("...") is used to indicate the rest of the cycle is omitted.


----------



## reThinking the Cube (Mar 6, 2010)

cuBerBruce said:


> reThinking the Cube said:
> 
> 
> > Nice work! These tables are very interesting.
> ...



Cycle structure file is remarkable. Great work once again, Bruce. Here is my 2-cents on how the case representations can be made less arbitrary, and maybe further reduced by 1-turn conjugation.

n = 6, 10 moves
(DFR FRD ...)(DRB BDR ...)
(DLF LFD ...)(DRB BDR ...)
*(ULB LBU ...)(DFR RDF ...)*
(DFR DRB)
(DLF RBD)
*(ULB DFR)*

n = 6, 11 moves
(DFR RBD)
(DLF DRB)

The bold ones above can be made equivalent to their respective n=6 cases, IF 1-turn conjugate moves are also allowed. It is interesting to note that the cross-cube swap (ULB DFR) can be oriented with just cube rotations, so that only 1 case is needed for all 5 of those corner 2-cycles. {(DFR DRB),(DLF RBD),*(ULB DFR)*,(DFR RBD),(DLF DRB)} Likewise the other 3 cases (corner twisters) can be reduced to 1 - (ULB LBU ...)(DFR RDF ...)

The reductions should be even more dramatic for n=4,5. At first, I wasn't sure if a system could be adopted to (non-arbitrarily) conjugate these for the purpose of representation, but I have an idea now. With n=4 cubes there are 6 patterns for the locations of the remaining unsolved pieces.

LL = (UFR, ULF, UBL, URB) 
TL = (UFR, ULF, DRF, URB) 
FL = (UBL, ULF, DRF, URB) 
XL = (UBL, ULF, DRF, DBR) 
SL = (UFR, ULF, DBR, URB) 
*ZL = (UFR, DRF, UBL, URB)* 

These unsolved piece patterns can all be made equivalent to each other by some 1-2 turn conjugate, but 2-turns would make actual case recognition very confusing. So for example, with LL as the base pattern, then the TL "Tripod" cases would 1st require 2-move conjugate turns (i.e. R' U' z') to form some equivalent LL case. Too messy to make sense of. But note that the SL and ZL patterns can always be conjugated to ANY of the others with just 1-turn! And since SL is by equivalencies = ZL, ALL the n>=4 cases could be represented by forcing the unsolved pieces by at most a 1-turn conjugation, +cube rotations, to occupy ONLY the locations in ZL = (UFR, DRF, UBL, URB). Maybe this is viable.

..


----------



## TCUBER (Mar 7, 2010)

TomZ said:


> The distribution of positions on the 2x2x2 that have at least 2/8 pieces solved is:
> 
> 
> ```
> ...


It is 2-45!*8 
So I have to agree with you


----------



## cuBerBruce (Mar 8, 2010)

reThinking the Cube said:


> The reductions should be even more dramatic for n=4,5. At first, I wasn't sure if a system could be adopted to (non-arbitrarily) conjugate these for the purpose of representation, but I have an idea now. With n=4 cubes there are 6 patterns for the locations of the remaining unsolved pieces.
> 
> LL = (UFR, ULF, UBL, URB)
> TL = (UFR, ULF, DRF, URB)
> ...



I note that you're missing the (ULF, URB, DRF, DLB) case, and that case is only adjacent to XL. I also note that SL and ZL are mirrors of each other, so they are really the same case when reducing by symmetries of the cube.

So I can probably sort out the positions in the file, particular which ones are SL/ZL and the (ULF, URB, DRF, DLB) case, and similarly sort out for the n=5 and n=6 positions.

For n = 5, I get three cases, one of which is adjacent to the other two.



reThinking the Cube said:


> *Bruce, could you generate for the #of moves away, all 3674160 are from any n>=4 position? That would reveal the potential for human transitions into the easier known cases.*



It was rather easy to alter my code to treat all positions with 4 or more pieces solved with respect to each other as if they were "solved," and perform a breadth-first search to calculate how many moves are required to get to this (funny notion of) "solved" from each possible state.


```
Number of moves required to get at least 4 cubies of the 2x2x2 solved
with respect to each other, in terms of number of positions and
number of positions as reduced by symmetry and antisymmetry.

moves   positions    reduced
-----   ---------    -------             
  0         34786        529
  1        247092       2863
  2        961942      10606
  3       1884540      20389
  4        544192       5884
  5          1608         25
          -------      -----
total     3674160      40296
```

The 25 cases requiring 5 moves correspond to these positions (in cycle notation).


```
(UFL LUF ...)(URF LBU LFD FRD RFU ...)(UBR RBD)
(UFL RUB DRB BUL FUR LFD RDF)
(UFL BUL UBR URF)(DLF DRB LFD ...)(DFR RDF ...)
(UFL FLU ...)(URF DFR DRB LFD LBU UBR FUR ...)
(UFL FRD ULB FLU ...)(URF DLF UBR)(DRB BDR ...)
(UFL URF BDR FLU ...)(UBR LBU LFD BRU ...)(DFR FRD ...)
(UFL BUL FDL UBR URF BDR FLU ...)(DFR RDF ...)
(UFL FDL UBR FLU ...)(URF RFU ...)(ULB DRB DFR LBU ...)
(UFL FRD BRU FLU ...)(URF FDL ULB RFU ...)(DRB RBD ...)
(UFL BRU RFU FLU ...)(ULB RDF LBU ...)(DLF FDL ...)(DRB BDR ...)
(UFL RBD LBU FUR RDF FLU ...)(DLF FDL ...)
(UFL RUB RFU FLU ...)(ULB RDF BUL ...)(DLF FDL ...)(DRB RBD ...)
(UFL DRB LUF ...)(URF BRU)(ULB LBU ...)(DLF DFR)
(UFL UBR LUF ...)(URF RDF DRB FDL FUR ...)(ULB BUL ...)
(UFL BRU LUF ...)(URF DRB FDL FUR ...)(ULB FRD BUL ...)
(UFL FDL BDR UBR FLU ...)(URF RFU ...)(ULB BUL ...)(DFR RDF ...)
(UFL DLF BDR RUB)(ULB LBU ...)(DFR RDF ...)
(UFL RDF)(UBR DLF)(ULB BDR)
(UFL LUF ...)(URF BUL RDF FDL RFU ...)(UBR RBD)
(URF FUR ...)(ULB FRD LBU ...)(DLF FDL ...)(DRB RBD ...)
(UFL LBU LUF ...)(UBR BRU ...)(DLF FDL ...)(DFR BDR FRD ...)
(UFL DRB)(UBR BUL DLF FRD)
(UFL LBU RDF FDL BDR BRU LUF ...)(URF RFU ...)
(UFL LBU FRD LFD URF DRB RUB)
(UFL LBU RDF LFD URF DRB RUB)
```


----------



## Gaétan Guimond (Mar 11, 2010)

The heart of the cube is the 8 corners because it's number can not change. 
Pure system http://pages.videotron.com/toulou/gaetan/

The cube popularity took a dive after hungary budapest championship of the world in 1982. The return in competition after 21 years was the world championship in toronto canada in 2003. Exactly had the same place at the science fair my web page photo that I placed on my web site that I took on the national championship of 1982.

The name of my domain rubikscuberecord.com and I'm the only one to have solved the cube blindfolded. If you don't believe in the one that has brought back the cube you will have to answer to the irreversables evidence. Contrary to it's return in 2003 in the store where the cube sales were influenced by the championship wich was not the case in 1982.

The cube is'nt musical (method & math) partition exchange only but it's has competitive. 

The cube is a puzzle where the genius of the teenager's suffice to reach world records. I never said that it was not for children or adults because human curiosity has no age. 

The emails that I kept in my reception box before 2003 from hotmail speak for themselves. Journalists outside the province of quebec never heard from me because the cuber's of my generation present on the web before 2003 never told my name with my story. People are sold by popular culture.

http://www.youtube.com/watch?v=iE1RH2S1fWQ


----------



## ShadenSmith (Mar 11, 2010)

I love you Guimond.


----------



## Stefan (Mar 11, 2010)

He's back! Pointless as always!



Gaétan Guimond said:


> The emails that I kept in my reception box before 2003 from hotmail speak for themselves.



The emails you *didn't* get *after* 2003 also speak for themselves.


----------



## reThinking the Cube (Mar 12, 2010)

StefanPochmann said:


> He's back! Pointless as always!



Exactly what I was thinking _at first_, but then I began to wonder what he was trying to get at here...



Gaétan Guimond said:


> The heart of the cube is the 8 corners because it's number can not change.
> Pure system http://pages.videotron.com/toulou/gaetan/



You should take a closer look! After deciphering, this reveals itself to be an ingenius way to represent the corner pieces for all cubes, and a demonstration for solving ANY corner position with at most 3 face turns (i.e. X=F,Y=U,Z=R). It looks to me like the pyramid could be assigned as (1=UBL, 2=ULF, 3=URB, 4=DFL, 5=DRF, 6=DBR, and UFR is the picture =(0)). DLB would be the solved reference piece. Using this idea, all corner cases can be represented using only 6 positions, since 2 (UFR, DLB) are always solved by default. I have the thought now, that the 6 positions can be seen as arranged in a hexagon around UFR (instead of a pyramid). This is inspiring towards a better system for representing all corner cases.

..


----------



## reThinking the Cube (Mar 12, 2010)

cuBerBruce said:


> *So I can probably sort out the positions in the file, particular which ones are SL/ZL and the (ULF, URB, DRF, DLB) case, and similarly sort out for the n=5 and n=6 positions.*



I am very much looking forward to this. For convenience let's make DL = (ULF,URB,DRF,DLB). Good job spotting the previous oversite. If possible, you could even use up to a 2-move conjugation for reducing, since the main value of this is to get numbers for the fewest possible cases that are required to represent them all. How they are actually represented, or solved is of secondary importance. Just to have the list reduced to a reasonable minimal number of cases to get all n=>4 positions would be very sweet. Guimond's post has also given me an idea on how to better represent in a non-arbitrary way, but I am still rethinking on this one.



cuBerBruce said:


> reThinking the Cube said:
> 
> 
> > Bruce, could you generate for the #of moves away, all 3674160 are from any n>=4 position? That would reveal the potential for human transitions into the easier known cases.
> ...




*That is very significant! Over 85% transition to some n=>4 case in 3 moves or less. Could you also do this calculation for some of the n=1 positions below - especially the bolded one?*


```
moves   n=1      n=2      n=3      n=4      n=5      n=6      n=8   totals   n >= 2

 0        0        0        0        0        0        0        1        1        1
 1        0        0        0        9        0        0        0        9        9
 2        0       54        0        0        0        0        0       54       54
 3       48      186        0       87        0        0        0      321      273
 4      264      956      528       99        0        0        0     1847     1583
 5     1092     6302     1944      654        0        0        0     9992     8900
 6     7092    35976     6408      660        0        0        0    50136    43044
 7    44904   151900    26592     3948      192        0        0   227536   182632
 8   186864   577424    99688     5328      768        0        0   870072   683208
 9   [B][SIZE="2"]451728[/SIZE][/B]  1235424   186288    13524      784        0        0  1887748  1436020
10   151512   401360    62496     7932      384      116        0   623800   472288
11      240     1776      328      276        0       24        0     2644     2404
     ------  -------   ------    -----      ---      ---        -  -------  -------
     843744  2411358   384272    32517     2128      140        1  3674160  2830416

Edit: average number of moves added, per Stefan's request
     8.8199   8.7447   8.6894   8.6794   8.6391  10.1714   0.0000   8.7556   8.7364
```

...


----------



## cuBerBruce (Mar 13, 2010)

reThinking the Cube said:


> *Could you also do this calculation for some of the n=1 positions below - especially the bolded one?*



OK, first I did this for all n=1 positions. So I considered all positions with no two pieces solved with respect to each other as "solved." So not even the solved position is considered "solved." I then did a breadth-first search to determine number of moves to reach one of these positions from every possible position.


```
moves  positions  cumulative
  0       843744      843744
  1      2021802     2865546
  2       800585     3666131
  3         8029     3674160

Average number of moves = 0.9926
```

Next I did the same for only the n=1 postions that are 9 moves from the solved position (as this seems to be what reThinking the Cube asked for). Note there is one position that requires nine moves to reach one of these positions. I hope you can figure out what position that is.


```
moves  positions  cumulative

  0       451728      451728
  1      1772136     2223864
  2      1349636     3573500
  3        88180     3661680
  4        10240     3671920
  5         1844     3673764
  6          329     3674093
  7           57     3674150
  8            9     3674159
  9            1     3674160

Average number of moves = 1.3033
```

I'll try to get the categorized list of the cases for 4 or more solved pieces later this weekend.


----------



## reThinking the Cube (Mar 13, 2010)

cuBerBruce said:


> Next I did the same for only the n=1 postions that are 9 moves from the solved position (as this seems to be what reThinking the Cube asked for). Note there is one position that requires nine moves to reach one of these positions. I hope you can figure out what position that is.



Good trivial question, but I should have been more specific earlier. 
*
I want to compare the following results for (n=any, m=any) 3674160 positions - *



> Bruce, could you generate for the #of moves away, all 3674160 are from any n>=4 position? That would reveal the potential for human transitions into the easier known cases.





> Number of moves required to get at least 4 cubies of the 2x2x2 solved with respect to each other,in terms of number of positions and
> number of positions as reduced by symmetry and antisymmetry.
> 
> 
> ...





> That is very significant! Over 85% transition to some n=>4 case in 3 moves or less.




*- with the results that would be generated, for the (n=1, m=9) 451728 positions in this table. *


```
moves   n=1      n=2      n=3      n=4      n=5      n=6      n=8   totals   n >= 2

 0        0        0        0        0        0        0        1        1        1
 1        0        0        0        9        0        0        0        9        9
 2        0       54        0        0        0        0        0       54       54
 3       48      186        0       87        0        0        0      321      273
 4      264      956      528       99        0        0        0     1847     1583
 5     1092     6302     1944      654        0        0        0     9992     8900
 6     7092    35976     6408      660        0        0        0    50136    43044
 7    44904   151900    26592     3948      192        0        0   227536   182632
 8   186864   577424    99688     5328      768        0        0   870072   683208
 9   [B][SIZE="2"]451728[/SIZE][/B]  1235424   186288    13524      784        0        0  1887748  1436020
10   151512   401360    62496     7932      384      116        0   623800   472288
11      240     1776      328      276        0       24        0     2644     2404
     ------  -------   ------    -----      ---      ---        -  -------  -------
     843744  2411358   384272    32517     2128      140        1  3674160  2830416

Edit: average number of moves added, per Stefan's request
     8.8199   8.7447   8.6894   8.6794   8.6391  10.1714   0.0000   8.7556   8.7364
```


*The purpose, is to determine the relative difficulty for human transposition into the n=>4 cases, starting from scrambles that are n=1, as opposed to scrambles that are n=any. *

...


----------



## cuBerBruce (Mar 14, 2010)

OK, I believe what reThinking the Cube wants is for each set of positions in the table giving how many positions at each distance from solved for each n value, to further break down these sets of positions by how many moves they are from at least 4 pieces being solved. For the specific case of n=1 and 9 moves from solved, the breakdown is


```
moves
from              reduced
n>=4   positions   cases
------ ---------  -------
  2       72768      793
  3      269208     2861
  4      109224     1159
  5         528        7
         ------     ----
total    451728     4820
```
For the complete set of n=1,2,3 values, see the spoiler below.



Spoiler



"n" is the maximum number of pieces solved with respect to each other

"distance from n >= 4" is the number of moves (HTM) required to get
at least four pieces solved with respect to each other.

"distance from solved" is the number of moves (HTM) required to reach
the solved state.

"positions" is the number of 2x2x2 positions meeting the given conditions.

"reduced cases" is the symmetry/antisymmetry-reduced number of equivalence
classes for these positions.


```
distance   distance
        from       from                 reduced
 n     n >= 4     solved    positions    cases
===   ========   ========   =========   =======
 1         2         3           48         3
 1         2         4          264         7
 1         2         5          744        16
 1         2         6         1620        26
 1         2         7        11856       140
 1         2         8        31848       358
 1         2         9        72768       793
 1         2        10        33696       381
 1         2        11          192         2
 1         3         5          348         8
 1         3         6         4368        55
 1         3         7        23784       270
 1         3         8       114312      1214
 1         3         9       269208      2861
 1         3        10        82848       885
 1         3        11           48         1
 1         4         6         1104        12
 1         4         7         9264       101
 1         4         8        40512       428
 1         4         9       109224      1159
 1         4        10        34728       373
 1         5         8          192         2
 1         5         9          528         7
 1         5        10          240         3

 2         1         2           54         4
 2         1         3          186         7
 2         1         4          246         7
 2         1         5          390        13
 2         1         6         5256        68
 2         1         7         9768       132
 2         1         8        25656       300
 2         1         9        53624       628
 2         1        10        31528       379
 2         1        11          672        12
 2         2         4          686        15
 2         2         5         3432        47
 2         2         6        12360       149
 2         2         7        52332       578
 2         2         8       165152      1801
 2         2         9       366496      3948
 2         2        10       122880      1386
 2         2        11          568        13
 2         3         4           24         2
 2         3         5         2480        38
 2         3         6        15864       186
 2         3         7        74800       836
 2         3         8       310168      3324
 2         3         9       632520      6808
 2         3        10       193400      2139
 2         3        11          528        10
 2         4         6         2496        31
 2         4         7        15000       164
 2         4         8        76184       826
 2         4         9       182560      1965
 2         4        10        53448       594
 2         5         8          264         4
 2         5         9          224         4
 2         5        10          104         3
 2         5        11            8         1

 3         1         4          528         7
 3         1         5         1152        13
 3         1         6         2856        34
 3         1         7         8064        89
 3         1         8        30960       331
 3         1         9        54192       588
 3         1        10        21840       248
 3         1        11          120         3
 3         2         5          192         2
 3         2         6         1776        19
 3         2         7         5568        62
 3         2         8        19680       214
 3         2         9        43488       475
 3         2        10        14232       169
 3         2        11           64         2
 3         3         5          600         8
 3         3         6         1488        16
 3         3         7        11280       123
 3         3         8        43512       466
 3         3         9        79704       868
 3         3        10        23160       269
 3         3        11           96         2
 3         4         6          288         3
 3         4         7         1680        19
 3         4         8         5536        62
 3         4         9         8904       107
 3         4        10         3216        39
 3         4        11           48         1
 3         5        10           48         1
```




EDIT:
OK, I now have created a new version of the "4_or_more_solved" file that is sorted by the pattern of unsolved piece positions. The cycle notation is preceded by [letter,number] where letter indicates the pattern of unsolved pieces and the number is the distance from solved. (I have picked out letters to use for the n=5 and n=6 cases - V,P,K and I,A,C.)


----------



## reThinking the Cube (Mar 16, 2010)

cuBerBruce said:


> OK, I believe what reThinking the Cube wants is for each set of positions in the table giving how many positions at each distance from solved for each n value, to further break down these sets of positions by how many moves they are from at least 4 pieces being solved. For the specific case of n=1 and 9 moves from solved, the breakdown is
> 
> 
> ```
> ...




Thanks Bruce, that is perfect. Your tables have shown that scrambles resulting in n=1, m=9 cases have considerably less easy solve potential than scrambles that are uniformly random.

(In the spoiler table above) I was now wondering how many cases have transposition to n=>4 end up being equivalent to minimum distance from solved. In other words, how many of these minimum move solves actually go directly to some n=>4 that ends up to be the shortest distance from solved anyway? Taking the first case as example - if it takes 2 moves to get to n=>4, and 3 moves to optimal solve, then the last move is the n=4, m=1 case, and therefore the transistion to n=>4 for this case must have been optimal. Another one that pops out at me is (n=1, m=11). So how many of these n=>4 transposition cases are optimal then? And if they are not optimal, how many moves are being added, by first transposing to a n=>4 case? 



cuBerBruce said:


> OK, I now have created a new version of the "4_or_more_solved" file that is sorted by the pattern of unsolved piece positions. The cycle notation is preceded by [letter,number] where letter indicates the pattern of unsolved pieces and the number is the distance from solved. (I have picked out letters to use for the n=5 and n=6 cases - V,P,K and I,A,C.)



Sorting the patterns this way is much easier to work with. Are you going to also attempt reducing these by conjugations?

...


----------



## Gaétan Guimond (Mar 17, 2010)

You should write a book with the following title .....

Giving his life to the Rubik's puzzle

By Stephan pochmann world record post message

...................................................................................

http://www.youtube.com/watch?v=DAMRPcICix4


----------



## rachmaninovian (Mar 18, 2010)

Dear Mr Guimond, you make no sense.

but i'm a fan of yours so please make your website public again.

otherwise you make no sense.

regards,
someone.


----------



## cuBerBruce (Mar 19, 2010)

reThinking the Cube said:


> I was now wondering how many cases have transposition to n=>4 end up being equivalent to minimum distance from solved. In other words, how many of these minimum move solves actually go directly to some n=>4 that ends up to be the shortest distance from solved anyway? Taking the first case as example - if it takes 2 moves to get to n=>4, and 3 moves to optimal solve, then the last move is the n=4, m=1 case, and therefore the transistion to n=>4 for this case must have been optimal. Another one that pops out at me is (n=1, m=11). So how many of these n=>4 transposition cases are optimal then? And if they are not optimal, how many moves are being added, by first transposing to a n=>4 case?



OK, I've started looking into this. First I note that for each position, there may be several optimal solutions to solve it and several optimal solutions for reaching an n>=4 case. One optimal path to n>=4 might be along the path to solve optimally, while another for the same position might not. If I am to assume we consider all optimal paths to n>=4 and see if at least one of them is along the optimal path to solve the position, then it looks to me like the answer is somewhere in the 9% to 10% range. If you choose an arbitrary optimal path to n>=4, then the chances of it being along an optimal path to solve the position is significantly smaller (about 3% I believe).

I also note that this property may not always be the same between a position and its inverse. Therefore, I need to consider the 77802 symmetry equivalence classes instead of the 40296 symmetry/antisymmetry equivalence classes.



reThinking the Cube said:


> Sorting the patterns this way is much easier to work with. Are you going to also attempt reducing these by conjugations?
> 
> ...



I note that a 1-move conjugation can always produce a type D,Z,P, or I case (or you could pick A or C in place of I). So a one-move conjugation allows you to at least limit the cases to these four sets of positions.

EDIT: My program has calculated 76994 symmetry-reduced cases for N={1,2,3}. Of these, there exists an optimal path to n>=4 that is also along the optimal path to solved for 7013 of the 76994 cases. This is approximately 9.11% of the symmetry reduced cases. This also corresponds to 328608 out of the 3639374 positions or about 9.03% of the n={1,2,3} positions.

For n=1, m=11, there are 6 symmetry-reduced cases, of which 2 have an optimal solution to n>=4 that is also along the optimal solve path. This corresponds to 96 out of 240 positions. Two symmetry-reduced cases have 1 optimal solution for n>=4 that is not along the optimal solve path. Two symmetry-reduced cases have 2 optimal solutions for n>=4 (2 moves). For one of these, both are along an optimal path, while for the other only one is along an optimal path. For the other two symmetry-reduced cases, there are 14 optimal solutions to n>=4 (3 moves), but none of them along an optimal path.

Some further detail for the n=1 m=11 cases: The two cases with one optimal solution for n>=4 (2 moves), the n>=4 positions reached are 10 moves from solved (while the initial positions were 11 moves from solved). For the two cases of 2 optimal solutions for n>=4, in one case both of these reduce the position from 11 moves from solved to 9 moves from solved, and in the other case, one of the cases reaches a position 10 moves from solved. Of the two cases with 14 optimal solutions (3 moves) for reaching n>=4, in one case 12 reach an m=9 position while 2 reach an m=10 position, while in the other case, 10 reach m=9 while 4 reach m=10.


----------

