I finally found a solution to the *M*_{12} Puzzle from sciam.com. A hideously inefficient solution, but it works.

Spoilery remarks below.

Kriz and Siegel point out that the technique usually used with Rubik’s cube — finding sequences of moves that alter only a few cubies while leaving the rest alone, then using those sequences to put cubies two or three at a time into their proper position and orientation — doesn’t map to *M*_{12}, because there are no group elements (other than the identity) that alter only a few numbers. Indeed, they tell us, aside from the identity, all group elements leave fewer than five numbers fixed. As a corollary, if you put five numbers into the proper positions, then the other seven numbers will also fall into place automatically.

What I found interesting is that I was able to attack this problem with a strategy essentially the *opposite* of what one uses with the cube — using sequences of moves that leave *few* numbers in place. Actually, on further thought, I do use such sequences at the start of solving Rubik’s cube, e.g. to solve a layer while not worrying about the effect on the other two.

Using Kriz and Siegel’s notation (though I really wish they hadn’t used **I** to denote a non identity element), note that **I**^{2} is the identity, as is **M**^{11}. That means all sequences of moves can be put in the form **M**^{n}**IM**^{p}**IM**^{q}**I**…**IM**^{r}, with optionally an **I** at the beginning and/or the end, where 1 <= *n, p, q, …, r* <= 10.

Working left to right, **1** can easily be put into the first position: do as many **M**s as needed to put **1** into position 12, then do **I**. Now **2** can be put into the second position by more repeated **M**s.

Now what? Well, consider what we just did: we used a move that leaves position 1 invariant (**M**) repeatedly to put **2** into position 2. If we had a sequence of moves that left positions 1 and 2 invariant, could we use it repeatedly to put **3** into position 3?

One such sequence is **MIM**^{3}**IM**^{2}**IMIM**^{7}. However, whereas **M**^{11} is the identity, this sequence gives the identity after only four repetitions. We can, however, find other independent sequences that leave positions 1 and 2 invariant (“2-invariants”), and using these sequences in various combinations we can find ways to move a number from any of positions 4 to 12 into position 3, while leaving **1** and **2** in positions 1 and 2.

Now the path is clear. Similarly find a couple of independent move sequences that leave positions 1 through 3 unchanged (“3-invariants”) — easier said than done, but not difficult; you can use combinations of 2-invariants to make 3-invariants — with which you can move **4** from any of positions 5 to 12 into position **4**. Likewise, use the 3-invariants to build 4-invariants, with which you can put **5** into position 5. And you’re done.

The invariants I came up with are ridiculously long. One of my 4-invariants, for instance, is, I think, 444 moves long. There must be much shorter ones… but what I’ve got works.

Having proved I could find the needed invariants by “hand” (assisted by the sciam.com Flash gadget), I then went ahead and wrote a Perl script to search for them. Using it I came up with a complete set whose longest invariant, the one producing the permutation (1 2 3 4 9 10 6 5 12 11 7 8), requires 25 moves — a considerable improvement. Using these one should be able to:

— place 1 in no more than 11 moves

— place 2 in no more than 10 moves

— place 3 in no more than 11 moves

— place 4 in no more than 20 moves

— place 5 in no more than 25 moves

giving 77 moves as an upper limit on God’s algorithm.

LikeLike

Good going. I wouldn’t touch this with a 10-pole filter.

LikeLike