Home »

The 4x4x4 centres can be solved in 22 moves

Submitted by jaap on Wed, 09/21/2005 - 02:47.
In the yahoo speedcubing forum Chris Hardwick asked a question about analysis of solving the centres of the 4x4x4 cube. I felt that it was an easy thing to look at using my own solving program, so here are the results.

Finding God's Algorithm for the centres only was too hard a task since there are 24!/4!^6 = 3246670537110000 possible centre arrangements. I therefore split it into two stages.

First of all, solving 2 particular opposite centre colours on the 4x4x4 cube, placing them on any 2 opposite faces.

depth 0, positions 6, total 6
depth 1, positions 36, total 42
depth 2, positions 624, total 666
depth 3, positions 10290, total 10956
depth 4, positions 136338, total 147294
depth 5, positions 1362756, total 1510050
depth 6, positions 9517212, total 11027262
depth 7, positions 28400748, total 39428010
depth 8, positions 12030624, total 51458634
depth 9, positions 24336, total 51482970

Note that there are 6 solutions to this problem since there are 6 faces where the first colour is allowed to end up (the second colour must then end up on the opposite face).
The above assumes that you have two particular colours you want to solve first. You may be able to shave a few moves off on average if you can choose a different pair of colours when one pair is too difficult.
BTW, I am using single slice q+h metric.


Suppose that 2 opposite centres are solved. Without disturbing these you can solve the other 4 centres. The results are:

depth 0, positions 4, total 4
depth 1, positions 12, total 16
depth 2, positions 144, total 160
depth 3, positions 1044, total 1204
depth 4, positions 6476, total 7680
depth 5, positions 44320, total 52000
depth 6, positions 253624, total 305624
depth 7, positions 1372656, total 1678280
depth 8, positions 6066480, total 7744760
depth 9, positions 18121248, total 25866008
depth 10, positions 26745272, total 52611280
depth 11, positions 10149368, total 62760648
depth 12, positions 302288, total 63062936
depth 13, positions 64, total 63063000

Note that this time there are 4 solutions, depending on the cube orientation around the previously solved axis. It may in some cases be possible to shorten a solution by temporarily disturbing the two already solved centres.

Put together, the above shows that the centres of a 4x4x4 can always be solved in at most 22 moves.

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

Extending Thistlethwaite's algorithm to 4x4x4

Submitted by cubex on Wed, 11/09/2005 - 08:04.
I haven't crunched the numbers but maybe the next step for 4x4x4 calculations would be extending thistlethwaite's algorithm, slice turns instead of face turns. Another idea is calculating God's Algorithm for the 4x4x4 squares group.

Mark
» login or register to post comments

Nested subgroups for 4x4x4

Submitted by Bruce Norskog on Tue, 02/07/2006 - 17:24.

When I first read Mark's suggestion to extend Thistlethwaite's algorithm to the 4x4x4, I thought he was suggesting generalizing each of the nested subgroups of Thistlethwaite's algorithm to similar "groups" for the 4x4x4, with corresponding slice moves included in each of the sets of generators. (Of course, the positions of a plain 4x4x4 cube do not form a group, but the 4x4x4 supercube is a group, and the plain 4x4x4 can be thought of as a set of positions acted upon by this group.) Calculating God's algorithm for the squares group would be a subproblem of this. Anyway, I soon realized a practical extension of the Thistlethwaite algorithm for the 4x4x4 would need to use other groups than those four, since two of them actually would be the entire 4x4x4 supercube group, effectively reducing it to a three-stage algorithm. I realized it might be even be necessary to use more than four stages, and it might not even include the 4x4x4 squares "group" as one of the sets.

I decided to use GAP to look at the 4x4x4 supercube, since the supercube positions form a group. Normally, the 4x4x4 supercube is said to have approximately 7.072*(10^53) positions since the orientation of the puzzle does not matter. However, when discussing groups generated with various sets of generators (where these generators are basic cube moves), the orientation does matter. The group where orientation does matter has 24 times more positions, or 1.697*(10^55).

There are many possible subgroups that could be used in a Thistlethwaite-like algorithm for the 4x4x4 supercube. I decided to focus on sets of nested groups that would include the squares group. For the squares group, the generators U^2, u^2, D^2, F^2, f^2, B^2, R^2, r^2, and L^2 are sufficient. I considered that no smaller groups needed to be considered (other than the trivial group of 1 element).

I found groups of twelve different sizes that were subgroups of the supercube, and of which the squares group was a subgroup. I have decided (for this discussion) to call representative groups of these J1 through J12, as given in the table below. The Squares group and the whole supercube group (which I'll denote as Gs) are also included in the table. I also attempted to figure out what the number of positions would be for the plain 4x4x4 with four indistinguishable centers of each color. But, I could be off a factor of 2 or 4 or so on these figures, so I put question marks by those numbers.

"Name"  Generators                        Approx. Size    Plain 4x4x4

Squares <U2,u2,D2,F2,f2,B2,R2,r2,L2>      9.393*(10^12)   1.5*(10^11) ?
J1      <U2,u,D2,F2,f2,B2,R2,r2,L2>       6.959*(10^20)   2.7*(10^18) ?
J2      <U,u2,D2,F2,f2,B2,R2,r2,L2>       2.923*(10^23)   3.2*(10^19) ?
J3      <U2,u,D2,F2,f,B2,R2,r2,L2>        8.594*(10^29)   8.4*(10^26) ?
J4      <U,u,D2,F2,f2,B2,R2,r2,L2>        1.083*(10^31)   5.9*(10^26) ?
J5      <U,u2,D2,F2,f,B2,R2,r2,L2>        8.133*(10^34)   6.1*(10^28) ?
J6      <U,u2,D2,F,f2,B2,R2,r2,L2>        7.894*(10^35)   5.9*(10^29) ?
J7      <U2,u,D2,F2,f,B2,R2,r,L2>         1.952*(10^39)   2.0*(10^31) ?
J8      <U,u,D2,F2,f,B2,R2,r2,L2>         1.055*(10^46)   1.1*(10^38) ?
J9      <U,u2,D2,F2,f,B2,R2,r,L2>         2.512*(10^43)   2.6*(10^35) ?
J10     <U,u,D2,F,f2,B2,R2,r2,L2>         2.308*(10^49)   2.4*(10^41) ?
J11     <U,u2,D2,F,f2,B2,R2,r,L2>         5.495*(10^46)   4.1*(10^40) ?
J12     <U,u2,D2,F,f2,B2,R,r2,L2>         8.966*(10^44)   9.4*(10^36) ?
Gs      <U,u,D2,F,f,B2,R,r,L2>            1.697*(10^55)   1.8*(10^47) (supercube)

In the sequences of nested groups below I also use these groups that are isomorphic to J1, J3 and J5, respectively.

  J1a: <U2,u2,D2,F2,f,B2,R2,r2,L2>
  J3a: <U2,u2,D2,F2,f,B2,R2,r,L2>
  J5a: <U,u2,D2,F2,f2,B2,R2,r,L2>

I looked for what possible sequence of nested groups might provide the most practical set of subproblems to solve. I have assumed that the number of positions in the subproblems would be the number of elements of the larger group divided by the number of elements in the smaller group. (Is this necessarily true for these groups?) I haven't worked out the actual number of positions that would be needed to be stored when computing God's algorithm for that stage. That number will generally be smaller than the factor listed since symmetry and antisymmetry can reduce the value by as much as a factor of 96 (approximately). Many of these subgroups will not be able to take advantage of all 48 symmetries of M, so a smaller reduction would apply in those cases.

Group     Size            Supercube Factor   Plain 4x4x4 Factor
-----     ----            ----------------   ------------------

----- Case 1 --------------------------------------------------
Gs        1.697*(10^55)
                             1,608,475,077   1.6*(10^9) ?
J8        1.055*(10^46)
                                 5,405,400   5.4*(10^6) ?
J7        1.952*(10^39)
                             2,271,491,040   2.4*(10^4) ?
J3        8.594*(10^29)
                             1,234,926,000   3.1*(10^8) ?
J1        6.959*(10^20)
                                74,088,000   1.9*(10^7) ?
Squares   9.393*(10^12)
                         9,393,093,476,352   1.5*(10^11) ?
I         1

Note: In the above, J8 -> J3 could possibly be done in one
step for the plain 4x4x4.

----- Case 2 --------------------------------------------------
Gs        1.697*(10^55)
                           675,559,532,340   6.8*(10^11) ?
J9        2.512*(10^43)
                               308,897,820   4.3*(10^6) ?
J5        8.133*(10^34)
                           278,269,992,000   1.9*(10^9) ?
J2        2.923*(10^23)
                            31,116,960,000   2.2*(10^8) ?
Squares   9.393*(10^12)
                         9,393,093,476,352   1.5*(10^11) ?
I         1

----- Case 3 --------------------------------------------------
Gs        1.697*(10^55)
                             1,608,475,077   1.6*(10^9) ?
J8        1.055*(10^46)
                           129,737,084,400   1.8*(10^9) ?
J5        8.133*(10^34)
                           278,269,992,000   1.9*(10^9) ?
J2        2.923*(10^23)
                            31,116,960,000   2.2*(10^8) ?
Squares   9.393*(10^12)
                         9,393,093,476,352   1.5*(10^11) ?
I         1

----- Case 4 --------------------------------------------------
Gs        1.697*(10^55)
                               308,897,820   4.3*(10^6) ?
J11       5.495*(10^46)
                           675,559,532,340   6.8*(10^11) ?
J5a       8.133*(10^34)
                           278,269,992,000   1.9*(10^9) ?
J2        2.923*(10^23)
                            31,116,960,000   2.2*(10^8) ?
Squares   9.393*(10^12)
                         9,393,093,476,352   1.5*(10^11) ?
I         1

----- Case 5 --------------------------------------------------
Gs        1.697*(10^55)
                               308,897,820   4.3*(10^6) ?
J11       5.495*(10^46)
                            69,604,975,440   7.0*(10^10) ?
J6        7.894*(10^35)
                         2,700,783,162,000   1.9*(10^10) ?
J2        2.923*(10^23)
                            31,116,960,000   2.2*(10^8) ?
Squares   9.393*(10^12)
                         9,393,093,476,352   1.5*(10^11) ?
I         1

----- Case 6 --------------------------------------------------
Gs        1.697*(10^55)
                                   735,471   7.4*(10^5) ?
J10       2.308*(10^49)
                                    25,740   2.6*(10^4) ?
J12       8.966*(10^44)
                             1,135,754,520   1.6*(10^7) ?
J6        7.894*(10^35)
                         2,700,783,162,000   1.9*(10^10) ?
J2        2.923*(10^23)
                            31,116,960,000   2.2*(10^8) ?
Squares   9.393*(10^12)
                         9,393,093,476,352   1.5*(10^11) ?
I         1

Note: In the above, Gs -> J12 could be done in one step with
a factor of 18,931,023,540.

----- Case 7 --------------------------------------------------
Gs        1.697*(10^55)
                             1,608,475,077   1.6*(10^9) ?
J8        1.055*(10^46)
                           129,737,084,400   1.8*(10^9) ?
J5        8.133*(10^34)
                       116,873,396,640,000   2.3*(10^10) ?
J1a       6.959*(10^20)
                                74,088,000   1.9*(10^7) ?
Squares   9.393*(10^12)
                         9,393,093,476,352   1.5*(10^11) ?
I         1

----- Case 8 --------------------------------------------------
Gs        1.697*(10^55)
                           675,559,532,340   6.8*(10^11) ?
J9        2.512*(10^43)
                        29,234,089,684,800   3.1*(10^8) ?
J3a       8.594*(10^29)
                             1,234,926,000   3.1*(10^8) ?
J1a       6.959*(10^20)
                                74,088,000   1.9*(10^7) ?
Squares   9.393*(10^12)
                         9,393,093,476,352   1.5*(10^11) ?
I         1

In summary, the above cases above have 5 or 6 stages. A 4-stage solution is not practical for the supercube, but it looks to me that a 5-stage solution is clearly achievable. A six-stage supercube solution can be done where only the last stage (the one solving within the Squares group) requires more than 2.9*(10^9) positions (Case 1). It doesn't look to me that a 4-stage solution for the plain 4x4x4 will be practical for any of these cases involving the squares group. There may be a better cases if you consider other possibilities than the Squares group for the last stage. The fourth root of 1.78*(10^47) is approximately 650*(10^9), so it would seem to me at least one stage of a four-stage approach would probably need to done with the use of disk storage.

I think I may be willing to work on this problem starting a few weeks from now, after I finish my current project. I don't know if Mark or anyone else has had any thoughts about what nested subgroups to use. It looks to me that Case 3 above would probably be the easiest to do, for either the normal cube or the supercube. Case 1 would seem to be a logical choice for an easier 6-stage solution.

- Bruce Norskog
» login or register to post comments