On this page I will try to explain how computers can be used in analysing the permutation groups that occur in puzzles. It is different from the Computer Puzzling page, as it is not strictly about searching for optimal solutions but about modelling a puzzle's group as a whole using the Schreier-Sims algorithm, and in the process finding non-optimal solutions to the puzzle.

**
Puzzle Algorithms
Stabiliser chains
Example
Improvements
**

The Rubik's cube has 43·10^{18} positions. We know this because we can

1. count all the possible positions that occur when taking apart and putting together the puzzle.

2. prove various restrictions on parity, edge flip and corner twist.

3. Give an algorithm to solve any position satisfying those restrictions.

How can we have a computer do something like this? It would be nice if we could just tell the computer how many pieces there are and what moves are possible, and that it could deduce from that how many positions there are, and how to solve it.

It would be exceptionally hard for it to do step 2 above, to literally find what restrictions there are and prove them. Instead, what is normally done is to get the computer to do only step 3, find an algorithm, and to do it in such a way that it is certain that it is complete, that there are no reachable positions that cannot be solved by that algorithm.

Now, let's see what a fixed Rubik's Cube algorithm might look like for a computer. It would have to be specified in every detail. Suppose for example that the algorithm would first put the correct edge piece at the UF position. There are 24 ways the edge can be situated (12 locations times 2 orientations), only one of which is correct. The first phase of the algorithm could simply be a list of 24 move sequences for all those cases, where one of the move sequences is empty (i.e. 'do nothing'). The next phase could be a list of 22 move sequences for the next edge piece, and so on all the way to the last piece of the cube. The last piece is automatically correct, so its list contains only the empty move sequence.

If you have an algorithm of this form, and if you somehow know it is complete, then there are many useful things you (or your computer) can do with it, such as:

- Find the number of possible positions. Just count the number of options in each phase, and multiply them together.
- Test if a particular position is solvable. Simply try to solve it with the algorithm. If in some phase the piece being solved lies at a location for which there is no sequence on the list for solving it, then the starting position was not legal. If it can be solved, then the algorithm gives an explicit method for solving it.
- Describe any position succinctly. Use the algorithm to solve it, and simply note which option is used in each phase. You can use the techniques explained in the indexing section of the computer cubing page to convert this into a single integer between 0 and the total number of positions.
- Generate any random solvable position, with each position equally probable. Just go through the algorithm, and at each phase choose one of the options on the list at random.

There now remains only the question of finding such a complete algorithm. For this we will need a little group theory.

Let G be the permutation group of the puzzle. After the first phase of the puzzle algorithm,
one of the pieces has been placed correctly, but the rest hasn't. What remains can be seen
as a smaller puzzle, with a permutation group G_{1}. Clearly G_{1}
is a subgroup of G, and it consists of all permutations in G that don't move that
first solved piece. G_{1} is called the **stabiliser** of that piece.

Thus the algorithm we are looking for consists of a sequence of nested groups:
G > G_{1} > G_{2} > .... > G_{n} = I.
Each group stabilises one more piece than the previous, and this is called a Stabiliser Chain.

Each phase of the puzzle algorithm also calls for a list of move sequences, one sequence for
each possible location of the piece being solved. If we have solved i pieces so far,
what is left is a permutation in G_{i}. We should be able to solve the next piece, so
one of the move sequences on the list for phase i will leave us with a permutation in G_{i+1}.
If the list of move sequences for phase i is r_{i1}, r_{i2}, r_{i3}, ... then
this means that every element in G_{i} lies in r_{ik}G_{i+1} for some k.
Thus the cosets r_{i1}G_{i+1}, r_{i2}G_{i+1},
r_{i3}G_{i+1}, ... together form the whole of G_{i}, or the
r_{ik} are a complete set of coset representatives for the cosets of G_{i+1}
in G_{i}.

Given the generators of G_{i}, it is relatively easy to find the set of coset
representatives r_{ij}. Suppose for the moment that the piece you are solving next is
already correct. Simply by trying all combinations of the generators of G_{i}, you fairly
quickly find ways to get that piece to any other place that it could be. By looking at
it in reverse, you have found ways to put the piece in its correct position wherever
it may be. In the next section this process will be illustrated with an example.

If we now had a way to find a set of generators for G_{i+1}, once we had the generators
of G_{i} and had found the coset representative r_{ij} of that phase, then we could
build up a stabiliser chain from left to right. This can be done because of the
Schreier subgroup lemma.

Schreier subgroup lemma:

Let G be a group with a set of generators S. Let H be a subgroup of G, and let R be the set of coset representatives of H in G. For any g in G, let [g] denote the element of R that represents the coset gH, i.e. [g]H = gH, and [g] lies in R.

Then H is generated by the set { [sr]^{-1}(sr) | r in R, s in S }.

Proof:

Let h be any element of H. Then it also lies in G, so h = s_{1}s_{2}s_{3}...s_{k}for some sequence of generators s_{i}in S.

Let t_{i}= [s_{i+1}...s_{k}], the coset representative of s_{i+1}...s_{k}.

Note that t_{k}= [e] = e by definition, and t_{0}= [s_{1}..s_{k}] = [h] = e.

So we can therefore rewrite h as h = (t_{0}^{-1}s_{1}t_{1})(t_{1}^{-1}s_{2}t_{2}) ...(t_{k-1}^{-1}s_{k}t_{k}).

We also find that (s_{i}t_{i})H = s_{i}(t_{i}H) = s_{i}( s_{i+1}..s_{k}H) = (s_{i}s_{i+1}..s_{k})H = t_{i-1}H so [s_{i}t_{i}] = [t_{i-1}] = t_{i-1}.

We use this to rewrite h once again, to get h = ([s_{1}t_{1}]^{-1}s_{1}t_{1})([s_{2}t_{2}]^{-1}s_{2}t_{2}) ...([s_{k}t_{k}]^{-1}s_{k}t_{k}).

The t_{i}are coset representatives (by definition) so clearly each factor in the above expression is of the form [sr]^{-1}(sr) with s in S and r in R.

Furthermore these factors are in H because [sr]^{-1}(sr) H = [sr]^{-1}(sr H) = [sr]^{-1}([sr]H) = ([sr]^{-1}[sr])H = eH = H.

Any element h in H is a product of such factors, so it follows that the set { [sr]^{-1}(sr) | r in R, s in S } will generate exactly H.

The construction of this stabiliser chain as described here is the **Schreier-Sims
algorithm**, and it forms the basis of all computational group theory.

Let's illustrate it with a small example that we can work out completely, namely the Rubik's Cheese. The six pieces are labelled A to F, and suppose we hold F still, and solve the other 5 pieces relative to it. The three generators of the group are the moves B (turning over ABC), C (turning over BCD) and D (turning over CDE).

In the first phase we will solve location E, so we have to determine where the piece
that belongs there could be. This is easy to find out by doing the reverse - start
with the correct piece at location E, try out all single moves to see where the piece
ends up. For each of those locations again try out every move, to get all the locations
that can be reached in two moves. Then another move, and so on until you find no more new
locations for the piece. In this way we get the orbit of the piece, and in this example
we get the following list:

E→E: -

E→c: D

E→C: DC

E→A: DB

E→a: DCB

E→e: DCD

I have used lower case letters to indicate when the piece is flipped. Note that applying a further move to any of these will not lead to another location, so no other locations can be reached by the piece.

Invert these sequences, and we can solve the first piece:

E→E: -

c→E: D

C→E: CD

A→E: BD

a→E: BCD

e→E: DCD

Now we have to apply Schreier's lemma to get generators for the group that remains.
In this case we have to combine the 3 generators of G with the 6 coset representatives
from the list above. For example, let's combine the generator D with the coset
representative BCD. Multiplying them gives DBCD, which is denoted by sr in
the lemma. We have to find which coset representative this permutation is similar to,
so we have to see which piece this permutation brings to location E. The sequence DBCD
brings the piece at location a to location E, and representative that does the same
thing is BCD. The lemma then says that (BCD)' DBCD, or DCBDBCD is one of the generators
of the group G_{1}, the stabiliser subgroup of G that keeps E fixed. You can easily check
that the move sequence indeed does not affect the piece at location E.

If we work out all 3×6 generators for G_{1}, then some of them will be the identity,
and there will no doubt be many duplicates. The lemma only guarantees that together
they generate the group G_{1}, not that they form a nice minimal set of generators. The
table below shows the results:

B | C | D | ||||
---|---|---|---|---|---|---|

E:- | B = | B | C = | C | D'D = | - |

c:D | (BD)'BD = | - | (CD)'CD = | - | - = | - |

C:CD | (BCD)'BCD = | - | D'D = | - | (DCD)'DCD = | - |

A:BD | D'D = | - | (BD)'CBD = | DBCBD | (BD)'DBD = | DBDBD |

a:BCD | (CD)'CD = | - | (BCD)'CBCD = | DCBCBCD | (BCD)'DBCD = | DCBDBCD |

e:DCD | (DCD)'BDCD = | DCDBDCD | (DCD)'CDCD = | DCDCDCD | (CD)'CD = | - |

The generators from this table are therefore:

B

C

DBCBD

DBDBD

DCBDBCD = B

DCDCDCD = C

DCBCBCD = DBCBD

DCDBDCD = DBDBD

Note that the last four are identical in effect to the first four, so they can safely be ignored.

The next phase is to solve piece D using these four generators. As before, we find
all the locations that piece D can get to if it were to start at its correct
location by applying the four generators.

D→D: -

D→b: C, or DBCBD

D→B: CB

D→d: CBC, or DBDBD

Inverting these gives the solution sequences for phase 2 of our algorithm.

D→D: -

b→D: C

B→D: BC

d→D: CBC

Again we apply Schreier's Lemma to get the generators of the remaining group.

B | C | DBCBD | DBDBD | |||||
---|---|---|---|---|---|---|---|---|

D:- | B = | B | C'C = | - | C'DBCBD = | CDBCBD | (CBC)'DBDBD = | CBCDBDBD |

b:C | (BC)'BC = | - | - = | - | (-)'DBCBDC = | DBCBDC | (C)'DBDBDC = | CDBDBDC |

B:BC | C'C = | - | (CBC)'CBC = | - | (CBC)'DBCBDBC = | CBCDBCBDBC | (BC)'DBDBDBC = | CBDBDBDBC |

d:CBC | (CBC)'BCBC = | CBCBCBC | (BC)'BC = | - | (BC)'DBCBDCBC = | CBDBCBDCBC | (-)'DBDBDCBC = | DBDBDCBC |

There are apparently 10 different generators in this table, but after removing those
that have the same effect as a shorter one, we are left with only three:

B

CDBCBD

CDBDBDC

The third phase is trying to solve piece C using these generators.

C→C: -

C→a: B

C→c: CDBCBD

C→A: CDBDBDC

Inverting these we get the solution sequences for this third phase:

C→C: -

a→C: B

c→C: DBCBDC

A→C: CDBDBDC

Once more we apply Schreier's lemma to get the generators of the remaining group.

B | CDBCBD | CDBDBDC | ||||
---|---|---|---|---|---|---|

C:- | B'B = | - | (DBCBDC)'CDBCBDC = | CDBCBDCDBCBDC | - = | - |

a:B | - = | - | (CDBDBDC)'CDBCBDB = | CDBDCBDB | (DBCBDC)'CDBDBDCB = | CDBCBDCDBDBDCB |

c:DBCBDC | (CDBDBDC)'BDBCBDC = | - | - = | - | (B)'CDBDBDCDBCBDC = | BCDBDBDCDBCBDC |

A:CDBDBDC | (DBCBDC)'BCDBDBDC = | CDBCBDBCDBDBDC | (-)'CDBCBDCDBCBD = | CDBCBDCDBCBD | - = | - |

It turns out that these generators all have no effect so the remaining group is trivial, and the last two pieces will automatically be solved now. Our complete chain now looks like this:

Stage: | 1 | 2 | 3 | total |
---|---|---|---|---|

Generators: |
B
C D |
B
C DBCBD DBDBD |
B
CDBCBD CDBDBDC | |

Coset representatives: |
E→E: -
c→E: D C→E: CD A→E: BD a→E: BCD e→E: DCD |
D→D: -
b→D: C B→D: BC d→D: CBC |
C→C: -
a→C: B c→C: DBCBDC A→C: CDBDBDC | |

Number of cosets: | 6 | 4 | 4 | 96 |

Average length: | 11/6 | 6/4 | 14/4 | 6.83 |

Maximum length: | 3 | 3 | 7 | 13 |

This shows that the Cheese has exactly 96 positions, and gives us a way to solve it in at most 13 moves, with an average of 6.83 moves.

Let's see what happens with a more difficult puzzle, the Rubik's Cube. The generators of G are of course the face turns of the cube. Let's solve the UF location first. As before we can easily find all the different places the UF edge piece can placed, and by doing the inverse of those move sequences we put the correct piece at UF wherever it may be. In this example you would find a list such as this:

UF→UF: - UF→UR: U UF→UB: U2 UF→UL: U' UF→LF: F UF→DF: F2 UF→RF: F' |
UF→FR: RU UF→DR: R2U (or D'F2) UF→BR: R'U UF→RB: BU2 (or R2F') UF→DB: B2U2 (or D2F2) UF→LB: B'U2 (or L2F) UF→BL: LU' UF→DL: L2U' (or DF2) UF→FL: L'U' UF→LU: LF UF→LD: L'F UF→RD: RF' UF→RU: R'F' |
UF→FD: FL'U' (or F'RU, DRF', D'L'F) UF→FU: FRU (or F'L'U', ULF, U'R'F') UF→BU: BLU' (or B'R'U, U'LF, UR'F') UF→BD: B'LU' (or BR'U, D'RF', DL'F) |

We can now apply the Schreier lemma to find generators of the group that remains once this first piece has been solved.

U | D | R | L | F | B | |
---|---|---|---|---|---|---|

UF: - | - | D | R | L | - | B |

UR: U | - | U'DU = D | - | U'LU | U'FU | U'BU |

UB: U2 | - | U2DU2 = D | U2RU2 | U2LU2 | U2FU2 | - |

UL: U' | - | UDU'= D | URU' | - | UFU' | UBU' |

LF: F | F'UF | F'DF | F'RF | - | - | B |

DF: F2 | F2UF2 | UL2DF2 | F2RF2 | F2LF2 | - | B |

RF: F' | FUF' | FDF' | - | FLF' | - | B |

FR: RU | U'R'URU | U'R'DRU | - | U'LU | - | U'R'BRU |

DR: R2U | U'R2UR2U | F2DR2U | - | U'LU | U'R2FR2U | U'R2BR2U |

BR: R'U | U'RUR'U | U'RDR'U | - | U'LU | U'RFR'U | UL'B2R'U |

RB: BU2 | U2B'UBU2 | U2B'DBU2 | FR2BU2 | U2B'LBU2 | U2B'FBU2 | - |

DB: B2U2 | U2B2UB2U2 | U'R2DB2U2 | U2B2RB2U2 | U2B2LB2U2 | U2B2FB2U2 | - |

LB: B'U2 | U2BUB'U2 | U2BDB'U2 | U2BRB'U2 | F'L2B'U2 | U2FU2 | - |

BL: LU' | UL'ULU' | UL'DLU' | URU' | - | UL'FLU' | - |

DL: L2U' | UL2UL2U' | U2B2DL2U' | URU' | - | UL2FL2U' | UL2BL2U' |

FL: L'U' | ULUL'U' | ULDL'U' | URU' | - | - | ULBL'U' |

LU: LF | U'R'F'ULF | F'L'DLF | F'RF | U2BL2F | F'L'FLF | F'L'BLF |

LD: L'F | F'LUL'F | UL'BDL'F | F'RF | - | F'LFL'F | F'LBL'F |

RD: RF' | FR'URF' | ULF'DRF' | U2B'R2F' | FLF' | FR'FRF' | FR'BRF' |

RU: R'F' | UL'B'UR'F' | FRDR'F' | - | FLF' | FRFR'F' | FRBR'F' |

FD: FL'U' | ULF'UFL'U' | F'LDFL'U' | ULF'RFL'U' | ULF'LFL'U' | ULFL'U' | ULBL'U' |

FU: FRU | FRUFRU | U'R'F'DFRU | U'R'F'RFRU | U'R'F'LFRU | ULF2RU | U'R'BRU |

BU: BLU' | F'L'UBLU' | UL'B'DBLU' | UL'B'RBLU' | UL'B'LBLU' | UL'FLU' | U'RB2LU' |

BD: B'LU' | UL'BUB'LU' | FR'DB'LU' | UL'BRB'LU' | UL'BLB'LU' | UL'BFB'LU' | - |

As you can see, there is a problem with Schreier's Lemma. The number of generators for each
successive G_{i} increases exponentially. For example, the lemma gives about 6*24
generators for G_{1} as seen above, and then 6*24*22 generators for G_{2},
and so on. Most of these generators are redundant, i.e. we can make do with far fewer of them.
For a practical method to build a solving algorithm, we need a way to reduce the number of
these generators.

When we build up the list of generators, we want to know if the next one we add is already in the group generated by the ones already on the list. If so, we don't need to add it after all as it is superfluous. Now, how do we check whether some permutation is in a group? We can do this if we had a complete stabiliser chain for that group, because then we can just see if it is a solvable permutation or not. Therefore instead of building each stage of the stabiliser chain separately, it is better to setup the whole chain first, initially with each stage containing no generators and only the identity as a coset representative. As we fill in the first stages, we update the later stages too. Each time we can test whether or not to add generator to a stage, as it either is already solvable and need not be added, or it is not solvable and will result in a new coset representative at some point along the way.

In this way we can gradually expand the lists of coset representatives and generators
for each stage in the stabiliser chain. The process ends when for every stage all
the generators from the Schreier lemma have been tested and shown to be solvable.
At that point the chain must represent the whole group. This is called the
**Incremental Schreier-Sims algorithm**. There are other techniques to limit the
number of generators, such as Jerrum's Filter which still allows you to build
the chain from left to right but uses fewer than n generators where n is the
number of pieces remaining.

There is a second problem with Schreier's Lemma. The length of the coset representatives and generators approximately doubles at each stage. If you are only interested in the group itself, for example its size and structure, rather than how each element can be decomposed as a sequence of moves then there is no problem. You need only keep track of permutations, not how they are represented. This way you can still test whether any permutation is in the group or not, and find the group's size.

There are many techniques for reducing the length of the generators and representatives. Take any fairly short scramble. If you try to solve this position by taking it through the stabiliser chain, there might be a point where the number of moves done so far (the scramble plus the moves solving the previous stages) is shorter than the coset representative for this position in the current stage. In that case you can replace that coset representative with the (inverse of) the move sequence done so far.

This is not likely to happen with any random position, as the average length of a coset representatives at any stage is approximately equal to the sum of the average lengths of all the previous stages. Nevertheless it can happen, especially if you try short commutators that move only few pieces that are solved in the later stages. It can therefore be beneficial to test all short move sequences, as well as all conjugated commutators ABCB'C'A' for all very short move sequences A, B, and C.

The order in which the pieces are solved can make a difference too. On the cube it is probably best to first solve a 2×2×2 block, because that still leaves three generators that do not affect the solved pieces. This allows the later stages to be done with combinations of those single-move generators rather than generators consisting of move sequences produced by the Schreier Lemma.

Even if the coset representatives are short, the solution method represented by a stabliser chain will generally not be very short, because it solves the pieces one by one in a fixed order. Short solutions are simply not what Schreier-Sims is good for.