Nearly every undergrad who takes abstract algebra learns the proof that the
15-puzzle cannot be solved if two of the tiles are reversed. That's because the permutations generated by the sliding motions are a subset of the entire permutation group (Sn), called the alternating group (An). The alternating group contains permutations that can be expressed as an even number of transpositions (called, unsurprisingly, "even permutations"), and a single-tile swap is an odd permutation.
So what if the motions are instead wraparound "slides"? That is, take an entire row or column and move it as many squares as you want, with tiles wrapping around from left to right or top to bottom. Does that set of moves produce the entire permutation group? Or is it the alternating group, or some other subgroup?
For odd-sized grids, the slide moves produce just even permutations. For example, sliding the top row on a 3x3 puzzle like this:
3 1 2
4 5 6
7 8 9
is the cycle (1 2 3) = (1 3)(1 2), which is even.
For even-sized grids it seems possible to generate a single-transposition--- say, (1 2)--- since the slides are odd permutations, but how to prove it?
Well, one way is brute force. For a 4x4 grid it might be just feasible to find the shortest "word" (combination of generating moves) which generates a particular transposition, although the search space is of size 16! =~ 2*10^13. I thought for a bit and bounded depth-first-search seemed better than BFS or heuristic search, because the queue size could become very large. But the size grows very quickly, even with two pruning heuristics at work.
The 8 basic moves on a 4x4 grid are H1, H2, H3, H4, V1, V2, V3, V4, where Hy slides the y'th row right by one, and Vx slides the x'th column down by one. The reverse moves can be generated by cycling around, i.e., H1^-1 = H1.H1.H1. So there are two easy ways to prune the DFS tree. The first is that we should never use the same move more than three times in a row. The second is that all the H's commute with each other (and so do all the V's), so we shouldn't explore both H3.H2.H1 and H1.H2.H3 since they are the same.
Depth # of words (w/o pruning commutative pairs)
4 2443 4673
6 95883 298057
8 3761907
10 147594811
12 5790738743
So much for brute force--- we didn't find (1 2) in this search, and going to 14 would take more than overnight.
But, that undergraduate algebra class probably talked about commutators as well, moves of the form y^-1.x^-1.y.x. In solving a Rubik's cube these moves tend to swap just a subset of the cubes, making it easier to find a move which fixes a portion of the cube while leaving the rest alone. The same is true here. (Note that composition of group operators is read from right to left.)
A useful commutator, X = V2^-1 . H1^-1 . V2 . H1 (first row right, second column down, first row left, second column up) introduces a 3-cycle among 1, 2, and 14:
*14 *1 3 4
5 6 7 8
9 10 11 12
13 *2 15 16
So V2.X.X produces the desired swap of 1 and 2, but has messed up the column:
[2 1] 3 4
5 *14 7 8
9 *6 11 12
13 *10 15 16
But, another three-cycle can be used to correct this. Let Z = V2^-1 . H3^-1 . V2 . H3, which looks like this:
1 2 3 4
5 *10 7 8
*6 *9 11 12
13 14 15 16
We just need to move the '10' into position, perform the cycle, and then back out again. That means something of the form Y^-1.Z.Y, where Y = V1^-1 . H4^-1. Here's Y alone:
5 2 3 4
9 6 7 8
14 10 11 12
1 15 16 13
which screws up a bunch of stuff, but here's Y^-1.Z.Y:
1 2 3 4
5 *10 7 8
9 *14 11 12
13 *6 15 16
which is a nice well-behaved three-cycle, exactly the one we want to patch up V2.X.X. Putting it all together, Y^-1.Z.Y.V2.X.X =
2 1 3 4
5 6 7 8
9 10 11 12
13 14 15 16
or in word form: H4.V1.V2.V2.V2.H3.H3.H3.V2.H3.V1.V1.V1.H
4.H4.H4.V2.V2.V2.V2.H1.H1.H1.V2.H1.V2.V2.V
2.H1.H1.H1.V2.H1. There might be a shorter word for the same permutation, but at 33 moves we were not likely to find this one by brute force any time soon.
But, this is sufficient to show that the slide moves generate the whole symmetric group S_16, since we can generate any other desired transposition in the same way, and the transpositions are generators for S_16.
How could we encode the directed search I performed by hand, into a computer algorithm for finding efficient (but not necessarily minimal) sets of moves for a given permutation?
tired