# 2x2x2 optimal tables - HTM, QTM, TTM



## Renslay (Sep 30, 2013)

I recently wrote an optimal solver in Matlab for the 2x2x2, and tested it with 3 different turn metric. Two of them are familiar, the HTM (half turn metric) and the QTM (quater turn metric), but I experienced a little with an other one, which I named TTM (tri-turn metric).

In HTM, you can do 9 movements in one step (U, U', U2, R, R', R2, F, F', F2).
In QTM, you can do 6 movements in one step (U, U', R, R', F, F').
In TTM, you can do 3 movements in one step (U, R, F).

So in TTM, the graph of the cube is directed, because for a scramble U (1 move), the inverse is U U U (3 moves).
(Note: technically, it is *not* a metric, because it's lack of symmetry...)

We know the distribution table for HTM and QTM, even the combined of the two:
http://www.jaapsch.net/puzzles/cube2.htm
(For example, there are exactly 12 states where HTM = 7 and QTM = 13)

So, as everybody knows, every cube can be solved with 11 HTM or 14 QTM. But what about TTM? Now, here is the result:


```
0 moves:           1
 1 moves:           3
 2 moves:           9
 3 moves:          27
 4 moves:          78
 5 moves:         216
 6 moves:         583
 7 moves:        1546
 8 moves:        4035
 9 moves:       10320
10 moves:       25824
11 moves:       62832
12 moves:      146322
13 moves:      321876
14 moves:      635632
15 moves:      988788
16 moves:      958176
17 moves:      450280
18 moves:       66420
19 moves:        1192
```

FUN FACTS:

There is no cube state that is hardest (i.e., it is the further from the solved state) in both three metrics. Moreover, there is no cube state which is hardest in both QTM and TTM metric.

However, there are a few "almost hardest case".

Number of states where HTM = max, QTM = max, TTM = max-1:
60
Such an example is R U' F' R2 U R F2 R' U' R2 U', which has the solutions:
U R2 U R F2 R' U' R2 F U R' (11f*)
U U R U U R' U F' U R' F R U U (14q*)
U U U R R F R U F U F R U U U F U R (18t*)

Number of states where HTM = max, QTM = max-1, TTM = max:
132
Such an example is the Y PLL, like F2 U' R U R F2 R U' R' U R', which has the solutions:
R U' R U R' F2 R' U' R' U F2 (11f*)
R U' R U U F U' F' R' F F R' F (13q*) - well, actually the previous HTM solution is also an optimal QTM solution
U F U F U U R R F U U F U R R R U R R (19t*)

Later maybe I do a 3D matrix filled with bubbles (different radiuses for different amounts) showing the combined distribution table similar the 2D in Jaap's page.


----------



## rokicki (Sep 30, 2013)

How about U, R, F'?

How about U, R, F2? U, R', F2?

What about U, R2, F2? Does that generate all states?


----------



## cuBerBruce (Sep 30, 2013)

Technically speaking, your "tri-turn metric" or "TTM" is not a metric.


----------



## Renslay (Sep 30, 2013)

rokicki said:


> How about U, R, F'?
> 
> How about U, R, F2? U, R', F2?
> 
> What about U, R2, F2? Does that generate all states?



Those are much more complicated "metrics". With U,R,F, cube ortations does not affect the length of the solution (if I'm right). But let's see U,R,F'. If I scramble the cube with U, then the solution is U U U _if the DBL cubie is fixed._ Otherwise, I can say x' F' x is a one move solution, and U,R,F' is equivalent to QTM.

But if we fix the DBL corner, I can say the distributions tomorrow. 



cuBerBruce said:


> Technically speaking, your "tri-turn metric" or "TTM" is not a metric.



I know and I edited that note shortly after the post:



Renslay said:


> (Note: technically, it is *not* a metric, because it's lack of symmetry...)


----------



## Renslay (Oct 1, 2013)

rokicki said:


> How about U, R, F'?
> 
> How about U, R, F2? U, R', F2?
> 
> What about U, R2, F2? Does that generate all states?



Thanks to your amazing suggestion for reorganizing the code, the runtime is just a few seconds, and I can 

give you the answers.

So, all the results here is for pure side rotations, _no cube rotation allowed._

(Note that the inverse is denoted by i, so R' = Ri. I was lazy to rewrote the output format of the program.)



Spoiler: U,R,F'





```
0           1
           1           3
           2           9
           3          27
           4          78
           5         227
           6         656
           7        1888
           8        5362
           9       14974
          10       41020
          11      109578
          12      277992
          13      627456
          14     1071345
          15     1042187
          16      440512
          17       40740
          18         105
```
First cube in the table with biggest distance:
U U U R R U Fi Fi U R R Fi Fi U R Fi R Fi (18)





Spoiler: U,R,F2





```
0           1
           1           3
           2           8
           3          22
           4          58
           5         151
           6         381
           7         943
           8        2316
           9        5652
          10       13691
          11       32943
          12       78120
          13      180218
          14      392323
          15      748792
          16     1076948
          17      876386
          18      252037
          19       13108
          20          59
```
First cube in the table with biggest distance:
U F2 U R U U R U F2 R F2 R U F2 U U R U R R (20)





Spoiler: U,R',F2





```
0           1
           1           3
           2           8
           3          22
           4          58
           5         152
           6         387
           7         969
           8        2414
           9        6002
          10       14856
          11       36547
          12       88882
          13      210330
          14      466493
          15      885939
          16     1171190
          17      702424
          18       86966
          19         517
```
First cube in the table with biggest distance:
U U U Ri U F2 U Ri U F2 Ri U Ri U U Ri U Ri Ri (19f)





Spoiler: U,R2,F2





```
0     1
     1     3
     2     7
     3    16
     4    36
     5    65
     6   120
     7   184
     8   276
     9   400
    10   488
    11   608
    12   652
    13   728
    14   700
    15   580
    16   156
    17    20
```
Note that this cannot solve every state - actually, this is only 5040 states, which is exactly factorial(7).
Which perfectly makes sense: you cannot rotate corners with <U,R2,F2>, but can permute all the elements. I know that you know it, this is essential in Kociemba's algorithm. So nice try.  I'm just disappinted in myself - I should have noticed the trick in the first place.
But anyway, nice to see the distribution table.
First cube in the table with biggest (finite) distance:
U U F2 U R2 U R2 U U U R2 U R2 U F2 U U (17f)


----------



## Stefan (Oct 1, 2013)

Renslay said:


> So, as everybody knows, every cube can be solved with 11 HTM or 14 QTM.



Constructive nitpicking: Unless you mean _"11 HTM or 14 QTM *or less*"_, I *don't* know it. There might be cases that can't be solved in exactly 11 HTM or can't be solved in exactly 14 QTM. I suspect 11 HTM is always possible because otherwise the WCA scrambler is flawed, but I don't k... oh wait, actually I do know about QTM. Yeah, there are plenty of cases that can't be solved in exactly 14 QTM. Now what about TTM?


----------



## Renslay (Oct 1, 2013)

Stefan said:


> Constructive nitpicking: Unless you mean _"11 HTM or 14 QTM *or less*"_, I *don't* know it.



Poor choice of words. I mean 11 HTM or 14 QTM at most.



Stefan said:


> There might be cases that can't be solved in exactly 11 HTM or can't be solved in exactly 14 QTM. I suspect 11 HTM is always possible because otherwise the WCA scrambler is flawed, but I don't k... oh wait, actually I do know about QTM. Yeah, there are plenty of cases that can't be solved in exactly 14 QTM. Now what about TTM?



Yeah, I know which cases you cannot solve with _exactly_ 14 QTM. 

I think I can modify my program to aswer the question. Instead of storing the distances in the table, I store a list (for every state). The list contains all the possible "exact distances". In the beginning, every list is empty, except the solved state (distance=0), which has the list {0}
Then the neigbours (distance=1) get {1}
...
for distance = d, I go through the states (which has a list), and add the {list+1} elements to the neigbour's list. For example, in the beginning, solved state has {0}, 2 iterations later will have {0,2} (coming from a neigbour with {1}), and so on.
When I reach 11, I can check which states can be reached (i.e., solved) with 11 HTM.


----------



## Stefan (Oct 1, 2013)

Renslay said:


> Yeah, I know which cases you cannot solve with _exactly_ 14 QTM.



I'm not so sure. Of course all odd parity cases can't be solved in 14 QTM, but can all even parity cases be solved in 14 QTM? Well, depends on how you count:



Renslay said:


> in the beginning, solved state has {0}, 2 iterations later will have {0,*2*}



That *2* is only possible if you allow something like *U U'*, which cancels and thus in my opinion should count as zero (btw, writing _"two iterations"_ looks nicer).

Similarly the 11 HTM question: You can reach any 10 HTM case _"in 11 moves"_ by using a 10 HTM generator and "duplicating" some move (e.g. turn *U* into *U' U2*) but that doesn't seem right.


----------



## Renslay (Oct 1, 2013)

Stefan said:


> That *2* is only possible if you allow something like *U U'*, which cancels and thus in my opinion should count as zero (btw, writing _"two iterations"_ looks nicer).
> 
> Similarly the 11 HTM question: You can reach any 10 HTM case by using a 10 HTM generator and "duplicating" some move (e.g. turn *U* into *U' U2*) but that doesn't seem right.



Well, that makes the question a bit harder...

And what if I store in a list for every elements the "last move", which caused that element to get into the list?
For example, I have the list for a cube state [C]: {1, 2, 2, 2, 4, 5}, and the corresponding last moves {U, R, U, F2, R, R}.
Then when I'm going to the next neighbour, [D], which is a U neighbour (so: [C] + U = [D], I won't put 1+1 (with U) and 2+1 (with U) into D's list, but I will put 2+1, 4+1 and 5+1 (all with U-s) into D's list.


----------



## rokicki (Oct 11, 2013)

Nice results! -tom


----------



## Renslay (Oct 14, 2013)

rokicki said:


> Nice results! -tom



Thanks.


----------

