Yay me

I finally found a solution to the M12 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 M12, 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 I2 is the identity, as is M11. That means all sequences of moves can be put in the form MnIMpIMqIIMr, 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 Ms as needed to put 1 into position 12, then do I. Now 2 can be put into the second position by more repeated Ms.

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 MIM3IM2IMIM7. However, whereas M11 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.

Advertisements

2 thoughts on “Yay me

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

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s