Home »

Square subgroup in QTM

Submitted by mdlazreg on Thu, 03/28/2013 - 19:44.
The square group analysis in HTM is as follow : 
        Analysis of the 3x3x3 squares group
        -----------------------------------

                                          branching
Moves Deep       arrangements (h only)     factor      loc max (h only)

  0                    1                      --             0
  1                    6                      6              0
  2                   27                      4.5            0
  3                  120                      4.444          0
  4                  519                      4.325          0
  5                1,932                      3.722          0
  6                6,484                      3.356          1  (6 X pattern)
  7               20,310                      3.132          0
  8               55,034                      2.709         65
  9              113,892                      2.069      1,482
 10              178,495                      1.567      7,379
 11              179,196                      1.004     25,980
 12               89,728                      0.501     50,320
 13               16,176                      0.180     11,328
 14                1,488                      0.092        912
 15                  144                      0.096        144
                 -------                                ------
                 663,552                                97,611
But I was not able to find a similar analysis in QTM. Does anyone have it? Is any code publicly available that will generate such QTM table as well as the distribution table of its cosets? Thanks.
» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Each half-turn is simply 2 quarter turns

Submitted by Bruce Norskog on Fri, 03/29/2013 - 09:31.

That HTM analysis assumes only doing moves that keep the state of the cube within the subgroup (half-turns only). A quarter turn applied to a squares group position always puts the cube outside the squares group. For QTM, you can restrict moves to half-turns only, and count each half-turn as two moves, so you simply double the distance values in the HTM distribution (with the counts remaining the same).

Now, you might be really interested in what the distribution is if you don't restrict the analysis to staying within the subgroup. Removing the restriction can be considered for face turn metric as well as for quarter turn metric. Kunkle/Cooperman's paper provides that distribution for FTM (as well as the half-turns only version) in symmetry reduced terms. Maximum depth is 13 moves.

I'm not aware this has been done for QTM. You could generate all symmetry representatives of the squares group and brute force solve each one with a QTM optimal solver (and then take into account the class size for each representative).

If you also want the distribution for getting a scrambled cube into the squares group, I imagine that's only been done for FTM. (See the Kunkle/Cooperman paper.) That has over a trillion symmetry-reduced positions.

» login or register to post comments

HTM of the square group

Submitted by mdlazreg on Fri, 03/29/2013 - 16:31.
Thank you Bruce again for making me aware of that analysis.
I am copying it here for an easy access: 
Square subgroup analysis using square moves only and all moves
0          1           1 
1          1           1
2          2           2
3          5           5
4         18          18
5         56          62
6        162         214
7        482         693 
8       1258        1871
9       2627        4093 
10      4094        5394  
11      4137        2774
12      2231         620
13       548           4
14       114    
15        16    
       15752       15752


Schreier coset of the square subgroup analysis
0                 1 
1                 1 
2                 3 
3                23 
4               241 
5              3002 
6             38336 
7            490879 
8           6298864
9          80741117
10       1028869318
11      12787176355
12     140352357299
13     781415318341
14     421980213679
15        330036864
16               17
      1357981544340 

And yes you are right I am interested in the QTM. The above is for HTM only.
Yes I started a brute force solve using Koceimba's optimal solver. However it is not as fast as I would like as it is solving them one by one. I was hoping I can use a coset solver that solves one coset at a time in a much faster way...
» login or register to post comments

Radu analyzed a larger group

Submitted by Bruce Norskog on Fri, 03/29/2013 - 23:55.

I don't know if you were trying to solve all elements of the group, or just the 15752 symmetry class representatives, but even that of course is still a rather large number to brute force. Still, I figured the positions were not generally very deep, so I think it should not be too huge a task to do the symmetry class representatives. A coset solver, if you can find an appropriate one or write one, should of course be a lot more efficient.

Searching back in the forum, I found this analysis of < U,D,L2,R2,F2,B2 > by Radu. The squares group is a subgroup of the group Radu analyzed, so all elements of the squares group are represented in Radu's analysis. The antipode of Radu's analysis is not an element of the squares group, and since all elements of the squares group are an even number of quarter turns from solved, that means 22q* is an upper bound for the elements of the squares group.

» login or register to post comments