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

 Subgroup Color Pattern Number of Elements Symmetry Type Symmetries H |H| = 8! * 8! * 4! / 2 = 19,508,428,800 D4h 16 Q |Q| = 4! * 4! * 4! * 4! * 4! / 2 = 3,981,312 = |H| / 4900 Oh 48 K |K| = 8! * 8! * 4! * 37 / 2 = 42,664,933,785,600 = |H| * 2187 D4h 16 T |T| = 4! * 4! * 4! * 8! * 37 / 2 = 609,499,054,080 = |K| / 70 Oh 48

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 H [G:H] = C(12,4) * 37 * 211 = 2,217,093,120 138,639,780 Q [G:Q] = C(12,4) *  C(8,4)2 * 37 * 211 = 10,863,756,288,000 = [G:H] * 4900 226,331,259,372 K [G:K] = C(12,4) * 211 = 1,013,760 =[G:H] / 2187 64,430 T [G:T] = C(12,4) * C(8,4) * 211 = 70,963,200 = [G:K] * 70 1,482,170

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>