Modeling subsets of the cube that involve ignoring certain cubies

I have an entire class library based around subsets of the cubies that I've used for a number of projects, and I use pretty much what Jaap has mentioned: positions of cubies rather than cubies at positions. I also have the various symmetry functions, canonicalization, inversion, masking, etc.

Unfortunately I was not able to make the classes as pretty as I wanted, so I ended up with a class for the edges, one for corners, and one for edges and corners; each of these three classes can have arbitrary cubies "masked out". I also have analogous permutation classes when I want to completely ignore the orientations (although I can mask the orientations out of the original classes, it's faster just to remove that logic entirely).

I've done a tremendous number of explorations of different cosets on the subsets of the cubies trying to find the "best" pruning tables for an optimal solver. One promising one is the space with all eight corners and two opposite edges. My own optimal solver is based on a coset that includes all 8 'U' cubies; this one works out pretty well in a number of ways.

I'd be happy to share my results of these coset spaces (their depth tables)---but there are so many it's hard to know which to share.

Jerry,

You are correct that H is usually not normal in these cases, and that G/H is therefore not a group but merely a coset space. In fact, the four stages of Thistlethwaite's algorithm are also coset spaces and not actually groups.

In some way you probably know all the stuff I'm going to write below, but I hope it helps you clarify your ideas a little.

Suppose H is the subgroup of G consisting of movements of those 6 corners only, leaving the rest fixed. Let g be any element of G, i.e. any permutation of the cube.

If we apply g to the Start position, we get some mixed position (which I'll also denote by g).
If we first apply some h in H to the start position (which mixes only the 6 corners) and only then do g, we get a similar position (denoted by hg). This differs from position g only in those 6 corner pieces, where ever they happen to actually be on the cube.

I am writing multiplication on the right here, so hg means apply h first and then g.

Anyway, we want to treat hg for any h in H the same as g itself. In other words, the coset Hg contains all the permutations that, when applied to Start, are considered the same as g.

Solving the puzzle in this context means applying moves to g until we get a position that is solved apart from those 6 corners.

So:

g.m1.m2.m3.....mn = h for some h in H.

or equivalently,

Hg.m1.m2.m3....mn = H

You thus start with Hg, multiply by m1 to get another coset H g1, multiply by m2 to get another coset H g2, and so on, until the coset you reach is H. This is the coset that contains the identity permutation.

Even though H is not a normal group, you can still work with its cosets. Multiplying on the right (i.e. performing some moves) gives you a new coset.


To put this in a program, you want a way to encode a position g such that hg would give the same answer for any h in H. In the example you would encode only the two other corners, i.e.

P = (location of corner 1)*7+(location of corner 2)
O = (orientation of corner 1)*3+(orientation of corner 2)
result = P*9+O.

This way all the elements of the coset Hg get the same number. It is a mistake to try to encode the piece at each location - instead encode the location of each (distinct) piece as in this example.

The standard techniques still apply in this situation. The positions /orientations of the pieces are converted into one or more coordinates, so that every puzzle position is given by such a set of coordinates. You can then:

- build transition tables (i.e. tables that give the new coordinate value resulting from applying any move to any previous coordinate value)
- build pruning tables (tables giving the distance to start for all values of some subset of the coordinates).
- build a God's Algorithm table (like a pruning table but giving the distance to start of all coordinate values, i.e. of all positions).


> conjugates

I don't know what you wish to do with conjugates, so I can't tell if you can still use them.

> symmetry

If H has symmetry, then you can exploit it. I think you will never have the full symmetry of G, unless H is normal.

> Sims tables

Sims tables normally encode which piece is at each location. What I did above is encoding the inverse, the location of each piece. The tail end of that encoding is the subgroup H which is simply chopped off.



I have written a program in Java, where you can define a puzzle:
- number of pieces of each type
- the number of possible orientations of each
- how many pieces are identical
- the effect of moves
- the starting position or positions
- which pieces to cluster together into coordinates for the transition tables
- which sets of clusters/coordinates to build pruning tables for

and then you can define a position and it will attempt to solve it with a pruned iterative deepening search. It does not exploit puzzle symmetry in any way (though clusters can share transition tables if they have the same number of pieces of the same type). It has been useful to me for my website, allowing me to find short move sequences for specific cases, and for calculating God's Algorithm in small puzzles. Unfortunately it tends to get bogged down for larger puzzles. As it doesn't exploit symmetry, it needs more pruning tables, and so they can't be as large.

Jaap's Puzzle Page:
http://www.geocities.com/jaapsch/puzzles/