Home »

The Void Cube to 13q

Submitted by B MacKenzie on Fri, 10/03/2014 - 19:12. 
Breadth First Enumeration
2014-09-27 19:58:23.094 VoidCubeClient[508:5903]  0             1             1
2014-09-27 19:58:23.095 VoidCubeClient[508:5903]  1             1            12
2014-09-27 19:58:23.099 VoidCubeClient[508:5903]  2             5           114
2014-09-27 19:58:23.101 VoidCubeClient[508:5903]  3            17         1,068
2014-09-27 19:58:23.105 VoidCubeClient[508:5903]  4           130         9,951
2014-09-27 19:58:23.133 VoidCubeClient[508:5903]  5         1,018        92,592
2014-09-27 19:58:23.333 VoidCubeClient[508:5903]  6         9,204       860,852
2014-09-27 19:58:25.033 VoidCubeClient[508:5903]  7        83,789     7,991,856
2014-09-27 19:58:40.300 VoidCubeClient[508:5903]  8       774,323    74,114,319
2014-09-27 20:01:03.984 VoidCubeClient[508:5903]  9     7,159,250   686,774,712
2014-09-27 20:25:47.908 VoidCubeClient[508:5903] 10    66,273,224 6,360,091,030


Coset Enumeration

Void Cube Model 1.0
	Group: R, U, F, TR, TU, TF
	Coset Base Subgroup: Subgroup with solved corner cubies and the
	   UF and UR cubies in the solved position regardless of orientation.
	484,989,120 cosets of size 7,431,782,400
	Coset Symmetry Reduction: Oh+

Cosets solved since launch: 3,429,943
Average time per coset: 0:00:00.068

Server Status:
Void Cube Enumerator Server

Enumeration to depth: 13

Snapshot: Friday, October 3, 2014 at 6:56:34 PM Central Daylight Time

 Depth             Reduced             Elements
   0                     1                    1 
   1                     2                   12 
   2                    18                  114 
   3                    50                1,068 
   4                   447                9,951 
   5                 2,008               92,592 
   6                19,000              860,852 
   7               124,184            7,991,856 
   8             1,136,806           74,114,319 
   9             9,028,936          686,774,712 
  10            82,411,850        6,360,091,030 
  11           711,657,402       58,868,124,048 
  12         6,507,640,604      544,562,369,684 
  13        58,275,341,089    5,033,855,951,932 
  
 Sum        65,587,362,397    5,644,416,382,171 

484,989,120 of 484,989,120 cosets solved

Elapsed Time: 0:12:14:50

This work was performed using the <R, U, F, TR, TU, TF> group model. This model was discussed in a previous thread. It must be pointed out here that the <R, U, F, TR, TU, TF> metric is exactly the same as the <R, U, F, L, D, B> metric since TR = L , TU = D and TF = B on the void cube. It makes no difference if the left face is rotated holding the rest of the cube rigid or if the left face is held rigid and the rest of the cube is rotated in the opposite direction, the rearrangement of the cubies is the same. If a distinct state of the void cube is at say depth 13 in the <R, U, F, TR, TU, TF> metric it will be at depth 13 in the <R, U, F, L, D, B> metric.

To establish a benchmark, I first performed a breadth first expansion of the move tree, storing the states generated as 20 byte arrays and counting the new states produced with each added turn. Using Oh symmetry reduction and antisymmetry the calculation could be completed to depth 10 before exhausting computer memory. A note about the symmetry reduction. All states in the <R, U, F, TR, TU, TF> group model have the DLB cubie in its starting position and orientation. In general, except for the C3v symmetries (the three fold rotations about the UFR‐DLB axis and the three planes of symmetry containing that axis), the cubic group conjugates will not have the DLB cubie in the proper location. This necessitates reorienting the conjugate. So the equivalence classes are formed by ( c * m' * g * m ) where g is a group element, m is a cubic group symmetry, and c the whole cube rotation required to orient the conjugate with the DLB cubie in the solved position and orientation.

To proceed further I went over to a coset solver approach. One partitions the group into cosets of a subgroup of that group and finds the depth of the coset members independently. Here one only has to keep track of previously solved states for the current coset which reduces the memory required to a manageable figure. The subgroup chosen was the subgroup whose members have the corner cubies solved and the UF and UR cubies in the solved position regardless of orientation. This yields cosets characterized by having a particular configuration of the corner cubies, a particular location for the UF cubie and a particular location for the UR cubie. This gives the partition:

7! * 36 * 12 * 11 = 484,989,120 cosets

10! * 211 = 7,431,782,400 elements per coset

The number of cosets needing to be solved may be reduced by symmetry reducing the corner configurations, again using the (c * m' * g * m) expedient used in the breadth first calculation. The corner configurations are partitioned into symmetry equivalence classes. One member is chosen from each class and composed with the UF, UR position configurations, yielding 132 cosets per equivalence class. These go to the coset solver and the results are multiplied by the size of the equivalence class.

The depth 13 calculation required twelve hours running on 8 cores spread over two computers. If I were inclined to do so, with the hardware at my disposal I could extend the calculation out to depth 14 with a four to five day run. Beyond this would take weeks extending into months and years and you're getting into the realm of super computers.

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

The Void Cube to 14q

Submitted by B MacKenzie on Fri, 10/10/2014 - 11:54.
Void Cube Enumerator Server

Enumeration to depth: 14

Snapshot: Friday, October 10, 2014 at 11:49:49 AM Central Daylight Time

 Depth             Reduced             Elements
   0                     1                    1 
   1                     2                   12 
   2                    18                  114 
   3                    50                1,068 
   4                   447                9,951 
   5                 2,008               92,592 
   6                19,000              860,852 
   7               124,184            7,991,856 
   8             1,136,806           74,114,319 
   9             9,028,936          686,774,712 
  10            82,411,850        6,360,091,030 
  11           711,657,402       58,868,124,048 
  12         6,507,640,604      544,562,369,684 
  13        58,275,341,089    5,033,855,951,932 
  14       533,731,791,005   46,478,587,568,902 

 Sum       599,319,153,402   52,123,003,951,073 

484,989,120 of 484,989,120 cosets solved

Elapsed Time 3:13:41:36
» login or register to post comments

Very nice

Submitted by rokicki on Thu, 10/16/2014 - 01:48.
Very cool; is this a generalized coset solver, or a special-purpose
program?

I'll try to check some of these numbers when I get time. Any comments
on comparing these numbers with the "equivalent" numbers for the
full cube? Is there anything we can infer with regard to minimal move
sequences that just move the centers (essentially)?
» login or register to post comments

Coset Solvers

Submitted by B MacKenzie on Thu, 10/16/2014 - 08:55.

I have a generalized framework for the coset solver. There are two different programs, the server and the client. The server parcels out the cosets to instances of the client and collates the results. The client requests cosets from the server, solves them and reports back to server. So, the user interface and code for communicating over the network are the same from application to application. The nitty gritty of defining the cosets, indexing schemes, move tables, pruning tables and the IDA solver are confined to separate modules which must be written more or less anew for each particular application.

Here's a comparison of the void cube to the standard cube:


 Void Cube Branch void/std Standard Cube Branch
0 1
1.000 1
1 12 12.00 1.000 12 12.00
2 114 9.50 1.000 114 9.50
3 1,068 9.37 1.000 1,068 9.37
4 9,951 9.32 0.994 10,011 9.37
5 92,592 9.30 0.987 93,840 9.37
6 860,852 9.30 0.979 878,880 9.37
7 7,991,856 9.28 0.972 8,221,632 9.35
8 74,114,319 9.27 0.964 76,843,595 9.35
9 686,774,712 9.27 0.957 717,789,576 9.34
10 6,360,091,030 9.26 0.949 6,701,836,858 9.34
11 58,868,124,048 9.26 0.941 62,549,615,248 9.33
12 544,562,369,684 9.25 0.933 583,570,100,997 9.33
13 5,033,855,951,932 9.24 0.925 5,442,351,625,028 9.33
14 46,478,587,568,902 9.23 0.916 50,729,620,202,582 9.32

It is perhaps counterintuitive that the counts for the void cube are such a large fraction of the counts for the standard cube since the order of the void cube is one twelveth that of the standard cube. Here in the early "exponential" portion of the distribution the branching factors for the two are fairly close. It is to be expected that as one proceeds out towards 17 and 18 moves the state space for the void cube will become filled more rapidly, more long period identities will be encountered, and the void cube distribution will level off while the standard cube distribution will continue to rise exponentially.

The minimum move sequences which move just the centers are the four spot and six spot maneuvers which are 12 and 8 q-turns respectively.

» login or register to post comments

Void Cube Identities

Submitted by B MacKenzie on Fri, 10/17/2014 - 08:17.

"The minimum move sequences which move just the centers are the four spot and six spot maneuvers which are 12 and 8 q-turns respectively."

On reflection, it follows that the two distributions can't diverge prior to depth 4 since this is the minimal depth at which two states may be 8 q–turns from one another. At depth 4 one begins to encounter identities on the void cube which are distinct states on the standard cube.

» login or register to post comments