Solving a reduced set cover problem

With the current hard- and software the set cover problem with 138,639,780 sets is too large to be handled.

The idea is to group H-cosets together into bigger sets, so that the set cover problem has a much smaller size. This can be done in a in a natural way by introducing two new subgroups K and T, closely related to the subgroups H and Q.

Color Pattern
Number of Elements
Symmetry Type


|H| = 8! * 8! * 4! / 2

= 19,508,428,800




|Q| = 4! * 4! * 4! * 4! * 4! / 2

= 3,981,312

= |H| / 4900



|K| = 8! * 8! * 4! * 37 / 2

= 42,664,933,785,600

= |H| * 2187



|T| = 4! * 4! * 4! * 8! * 37 / 2

= 609,499,054,080

= |K| / 70



The subgroup K can be described as the union of 2187 cosets of H having all possible 2187 corner orientations while the edges have the same properties as in the subgroup H.
The subgroup T derives likewise from the subgroup Q by dropping the restrictions on the corners. It is the union of C(8,4) * 2187 cosets of Q.

Now we list the properties of the corresponding cosets

Cosets of
Coset Example
Number of Cosets
Symmetry-reduced number


[G:H] =

C(12,4) * 37 * 211

= 2,217,093,120



[G:Q] =

C(12,4) *
 C(8,4)2 * 37 * 211

= 10,863,756,288,000 =

[G:H] * 4900


[G:K] =

C(12,4) * 211

= 1,013,760

=[G:H] / 2187



[G:T] =

C(12,4) * C(8,4) *


= 70,963,200

= [G:K] * 70


There are C(12,4) ways to position the red-green edges and 2^11 ways to flip the 12 edges which gives the number 1,013,760 of different K-cosets. The number of essentially different cosets reduced by the 16 D4h symmetries can be shown to be 64,430.

There are C(12,4) ways to set the position of the red-green edges and C(8,4) ways to set the position of the white-green edges, thus forcing the position of the white-red edges. There are 2^11 ways to flip the edges, so we have 495*70*2048 = 70,963,200 T-cosets. The number of essentially different T-cosets reduced by the 48 Oh symmetries can be shown to be 1,482,170.

It is important to observe that each coset of K splits into 70 cosets of T. If you take a look at the pattern example of a coset from K in the table above, there are 8 white edge facelets with the other edge facelet still grey. So you have C(8,4) ways to set the 4 missing red edge facelets and you have no choice left for the missing 4 green edge facelets.

The reduced set cover problem can be formulated in the following way:

Find a subset S of the 64430 essentially different K-cosets, each of them containing 70 T-cosets, such that all all 1,482,170 essentially different T-cosets are covered, in the sense that for each T-coset t there exists a symmetry m of Oh and a K-coset k of the subset S such that the coset m' * t * m (which is equivalent up to symmetry to t) is contained in k.

Each of the K-cosets splits again into 2187 H-cosets, and almost all of these H-cosets have to be solved to cover the whole cube space. Why not all 2187 H-cosets in all cases? This happens if the coset K has a D4h symmetry itself. Take for example the identity K-coset, which is the just the subgroup K itself. It has 16 symmetries, so there are up to 16 different H-cosets which are equivalent to each other.

All these H-cosets are in the same equivalence class for example.

With a randomized greedy algorithm the set cover problem could be solved with 25998 K-cosets. Representatives of all cosets are here. The number of H-cosets derived from these is a bit smaller than 25998*2187 for the reasons discussed above; it is exactly 55,882,296.

<previous>     <next>