# Square one can be solved in 31 moves in face turn metric



## qq280833822 (Dec 28, 2017)

In the past week, I have calculated the god's algorithm for square one in face turn metric (ftm). According to the calculation, any twistable square-one states can be solved no more than *31 moves*, where (x, 0), (0, y), / are counted as one move, (x, y) are counted as two moves.

In previous works, Mr. masonjones calculated the god's algorithm for sq1 in twist turn metric[1]. And Mike Godfrey solved all odd-permutation cube-shape positions and found that there're at least 12 positions cannot be solved in 30 moves in face turn metric[2].

Recently, I calculated the god's algorithm for sq1 in ftm. The number of different positions is 3,678 * 40,320 * 40,320 * 2 = 11,958,666,854,400, which is 3678 different shapes without considering middle layer and for each shape there are 40,320 * 40,320 combinations of permutations.
The number of positions is too large to handle, so I use symmetric reduction to reduce the search space. Firstly, all positions are split into 3678 * 2 * 2 sets according to shape, middle layer and parity, with 40320*20160 different positions per set. Then, I use symmetric to reduce the number of sets to 3816. Therefore the search space is reduced to 3816*40320*20160 = 3,101,840,179,200.
Finally, I use disk-based BFS search to calculate the god's algorithm. It spends 2 bits on each position. If the position have been visited, it stores the depth of the position modulo 3, otherwise it stores '3' to indicate the position has not been visited. So the total disk space required is 775,460,044,800 Bytes or 722.2GBytes.
After searching up to 31 moves, all positions have been accessed and therefore the god number of SQ1 is exactly 31.
Here's the depth distribution of all positions.


Spoiler





```
Depth          Total               #New
  0                    1                   1 
  1                   16                  15
  2                   85                  69
  3                  297                 212
  4                1,438               1,141
  5                5,371               3,933
  6               19,400              14,029
  7               63,588              44,188
  8              202,540             138,952
  9              649,260             446,720
 10            1,965,432           1,316,172
 11            6,140,878           4,175,446
 12           18,288,350          12,147,472
 13           56,172,978          37,884,628
 14          165,639,212         109,466,234
 15          498,518,504         332,879,292
 16        1,454,898,116         956,379,612
 17        4,285,819,784       2,830,921,668
 18       12,288,746,014       8,002,926,230
 19       34,951,544,310      22,662,798,296
 20       96,075,902,092      61,124,357,782
 21      257,070,679,994     160,994,777,902
 22      653,697,566,102     396,626,886,108
 23    1,581,344,013,920     927,646,447,818
 24    3,471,138,980,310   1,889,794,966,390
 25    6,600,087,749,620   3,128,948,769,310
 26    9,902,019,903,186   3,301,932,153,566
 27   11,668,654,358,130   1,766,634,454,944
 28   11,950,188,612,006     281,534,253,876
 29   11,958,657,866,914       8,469,254,908
 30   11,958,666,854,024           8,987,110
 31   11,958,666,854,400                 376
```




I also count the depth distribution of all 3816 unique sets. The value of cube-shaped odd-permutation sets matches the calculation of Mike Godfrey.

[1] Square One God's Algorithm Computed, http://cubezzz.dyndns.org/drupal/?q=node/view/35
[2] Odd Permutations of the Cube Shape of Square-1, http://cubezzz.dyndns.org/drupal/?q=node/view/77


----------



## sp3ctum (Jan 1, 2018)

Great work, thank you for sharing.

If I read your shape distribution data correctly, the most difficult cases require the 31 moves to solve, and there are exactly 376 of them.

Are these states in cubeshape or randomly shaped? I would imagine odd parity square square cases take more moves to solve, but I don't trust my intuition at all.


----------



## qq280833822 (Jan 1, 2018)

sp3ctum said:


> Great work, thank you for sharing.
> 
> If I read your shape distribution data correctly, the most difficult cases require the 31 moves to solve, and there are exactly 376 of them.
> 
> Are these states in cubeshape or randomly shaped? I would imagine odd parity square square cases take more moves to solve, but I don't trust my intuition at all.



Actually, there are 23 unique shapes with symmetry reduction or 68 shapes without considering symmetry that contains 31-depth positions.
An interesting thing is that all of these shapes have 4 corners on the top layer. Here is a list of these shapes and the number of 31-depth positions in each shape. The number before a shape is the number of different shapes that can be generated by the following shape according to symmetry (mirror and y2.)


Spoiler





```
shape                 #31-depth/shape
4 *  cceecece cececece -          4
4 *  cceecece ecececec /          8
4 *  cceeceec cececece -          3
4 *  cceeceec ecececec -          2
4 *  cceeecce ececceec -          4
4 *  cececcee ecececec /          8
4 *  cececece cceecece -          4
4 *  cececece cceeceec -          3
4 *  cececece ecceecec /          4
4 *  cececece ecececce /          4
1 *  cececece ecececec -         12
2 *  cececece ecececec /         16
2 *  ceceecce ecceecec -          2
2 *  ceceecec ceceecec -         28
1 *  ceceecec ceceecec /          8
4 *  ceceecec ceeccece -          1
2 *  ceceecec ececcece -         14
4 *  ceeceecc cececece -          2
2 *  ecceceec ceececce -          4
2 *  ecceecec ceceecce -          2
4 *  ecceeecc ceeccece -          4
1 *  ececcece ececcece /          8
1 *  ecececec cececece -         12
```


----------



## plutarch (Apr 25, 2020)

[Цитата= " qq280833822, сообщение: 1270354, участник: 1513"]
На самом деле, есть 23 уникальных формы с уменьшением симметрии или 68 форм без учета симметрии, которая содержит 31-позиции глубины.
Интересно то, что все эти фигуры имеют 4 угла на верхнем слое. Вот список этих фигур и количество 31-глубинных позиций в каждой фигуре. Число перед фигурой - это число различных фигур, которые могут быть созданы следующей фигурой в соответствии с симметрией (зеркало и y2.)
[Спойлер] [код] форма #31-глубина / форма
4 * cceecece cececece-4
4 * cceecece ecececec / 8
4 * cceeceec cececece-3
4 * cceeceec ecececec - 2
4 * cceeecce ececceec - 4
4 * cececcee ecececec / 8
4 * cececece cceecece - 4
4 * cececece cceeceec - 3
4 * cececece ecceecec / 4
4 * cececece ecececce / 4
1 * cececece ecececec - 12
2 * cececece ecececec / 16
2 * ceceecce ecceecec - 2
2 * ceceecec ceceecec - 28
1 * ceceecec ceceecec / 8
4 * ceceecec ceeccece-1
2 * ceceecec ececcece-14
4 * ceeceecc cececece-2
2 * ecceceecceecce - 4
2 * ecceecec ceceecce - 2
4 * ecceeecc ceeccece-4
1 * ececcece ececcece / 8
1 * ecececec cececece - 12
[/КОД] [/СПОЙЛЕР]
[/ЦИТАТА]
- Привет!
Можно ли получить скремблы из тех 376 позиций антиподов для квадрата-1, в которых решение равно 31 htm?
Они бы отлично боролись за упражнения в сборке квадрата 1 по количеству ходов.
С уважением и наилучшими пожеланиями


----------



## Filipe Teixeira (Apr 25, 2020)

plutarch said:


> [Цитата= " qq280833822, сообщение: 1270354, участник: 1513"]
> На самом деле, есть 23 уникальных формы с уменьшением симметрии или 68 форм без учета симметрии, которая содержит 31-позиции глубины.
> Интересно то, что все эти фигуры имеют 4 угла на верхнем слое. Вот список этих фигур и количество 31-глубинных позиций в каждой фигуре. Число перед фигурой - это число различных фигур, которые могут быть созданы следующей фигурой в соответствии с симметрией (зеркало и y2.)
> [Спойлер] [код] форма #31-глубина / форма
> ...


English:

In fact, there are 23 unique shapes with reduced symmetry or 68 shapes without symmetry, which contains 31-position depths. Interestingly, all these shapes have 4 corners on the top layer. Here is a list of these figures and the number of 31 deepest positions in each figure. The number in front of the figure is the number of different figures that can be created by the next figure in accordance with the symmetry (mirror and y2.)



Spoiler



4 * cceecece cececece-4
4 * cceecece ecececec / 8
4 * cceeceec cececece-3
4 * cceeceec ecececec - 2
4 * cceeecce ececceec - 4
4 * cececcee ecececec / 8
4 * cececece cceecece - 4
4 * cececece cceeceec - 3
4 * cececece ecceecec / 4
4 * cececece ecececce / 4
1 * cececece ecececec - 12
2 * cececece ecececec / 16
2 * ceceecce ecceecec - 2
2 * ceceecec ceceecec - 28
1 * ceceecec ceceecec / 8
4 * ceceecec ceeccece-1
2 * ceceecec ececcece-14
4 * ceeceecc cececece-2
2 * ecceceecceecce - 4
2 * ecceecec ceceecce - 2
4 * ecceeecc ceeccece-4
1 * ececcece ececcece / 8
1 * ecececec cececece - 12



Is it possible to get scrambles from those 376 antipode positions for square-1 in which the solution is 31 htm?
They would have fought well for the exercises in building square 1 in the number of moves.
best regards


----------



## plutarch (May 3, 2020)

Judging by the lack of an answer, I conclude that no studies have been conducted and all the hackneyed nonsense.


----------

