More In This Article
-
Overview
Simple Groups at Play
The M12 puzzle has 12 pieces arranged in a row and numbered 1-12 (see Fig. 1). There are two moves. The 'Invert' (I) move reverses the order of the pieces (Fig. 2) and the 'Merge' (M) move shuffles the pieces as a deck of cards (Fig. 3). The group of all possible moves we can get by repeating the I and M moves in arbitrary order is the Mathieu group M12. The 'Randomize' function displays a result of a random sequence of moves, and the player is supposed to reach the initial position by repeated use of the I and M moves.
To solve the M12 puzzle, it is convenient to represent moves in cycle notation. In this notation, in each parenthesis, each number is moved to the position of the next number, and the last number moves back to the first. Thus, for example, the I move is represented as
I = (1,12)(2,11)(3,10)(4,9)(5,8)(6,7)
and the M move as
M = (1)(2,3,5,9,8,10,6,11,4,7,12).
The strategy for solving the M12 puzzle is to device sequences of moves which accomplish particular tasks. The basic piece of information is that the group M12 can move any 5 numbers to any 5 positions in any orderchosen, but has precisely 12.11.10.9.8 elements, so the positions of all other numbers are determined by the positions of the first 5. Thus, if we can get, from a random position, the numbers 1, 2, 3, 4, 5 into their right places, the other numbers will fall into place automatically!
Now it is easy to get 1 into its right place: if it is not already there, move it to 12 by repeating the M move, and then get it to 1 by the I move. Furthermore, we can then get 2 to its right place by repeating the M move. When 1 and 2 are in their right places, consider the moves
X1=IM2IM5IM4=(1)(2)(8)(9)(3,10,4,5)(6,7,11,12)
and
X2=IMIM3IM2=(1)(2)(4,9)(3,11,10,5,8,7,12,6).
Clearly, if 3 is at the positions of 4, 5 or 10, we can get it to its right place by repeating X1. If it is in any other position except 9, we can get it back to its place by repeating X2. If it is at 9, we can use X2 to get it to 4, and then repeat X1 to get it to its right place.
With 1, 2 and 3 in place, consider the moves
Y1=IMIM3IM2IM9IM7IM8=(1)(2)(3)(4,7,6,12)(5,10,11,8,9)
and
Y2=IM3IM6IMIM9IM7IM8=(1)(2)(3)(4,7)(5,6)(8,12)(9,11,10).
If 4 is at any of the positions 6, 7, 12, we can get it to its place by repeating Y1. If it is at 5, 8, 9, 10, 11, we can repeat Y1 until it gets to 8, then use Y2 to get it to 12, and then Y1 to get it to its place.
Finally, with 1, 2, 3, 4 in place, consider the moves
Z1=IM9IM7IM8IM7IMIM5=(1)(2)(3)(4)(5,10,12,7)(6,8,11,9)
and
Z2=IMIM3IM2(IM7IMIM5)2=(1)(2)(3)(4)(5,11,12,6)(7,9,10,8).
If 5 is at 7, 10 or 12, we can repeat Z1 to get it to its place. If 5 is at 6,8,9 or 11, repeat Z1until it gets to 6, and then apply Z2 to get 5 to its right place, and complete the solution of the puzzle.
See what we're tweeting about
17 Comments
Add CommentDescription of Y1 is not quite right. It cycles (5, 10, 8, 9) but does not move 11.
Reply | Report Abuse | Link to thisDescription of Y2 is not quite right. It cycles (9, 11) but does not move 10.
If number 4 is in position 11, use Y2 to move it to position 9, then solve with Y1.
Here is another way to solve the M12 Puzzle.
Reply | Report Abuse | Link to thisDefine three Custom Moves:
F = (im3im6im)^4
B = (im)^4 im2im8
Cycle = (imm)^4 imim5
Starting with the solved state 1 2 3 4 5...
F gives 1 2 4 3 5...(exchanging the Front two of the Triad 3, 4, & 5).
Then B-F-B gives 1 2 3 5 4... (exchanging the Back two of the Triad 3, 4, & 5).
Together these two moves can give all six arrangements for positions 3, 4, & 5.
To solve the Puzzle:
Place numbers 1 and 2 as described in the article.
Use "Cycle" until one of the numbers 3, 4, or 5 appears in position 5.
Use "B-F-B" to move it to position 4.
Use "Cycle" until another of the numbers 3, 4 or 5 appears in position 5.
Use "B-F-B" either once or twice so that both selected numbers are in positions 3 and 4.
Use "Cycle" until the remaining number of 3, 4, and 5 appears in position 5.
Now place the numbers 3, 4 and 5 in their correct sequence as follows:
If 5 is not yet in place, use "B-F-B" once or twice until it is in place.
If 3 & 4 are not yet in place, use "F" and the Puzzle is solved.
Here is another way to solve the M12 Puzzle using "Restricted Moves", each of which taken alone gives a visually pleasing and highly symmetrical result:
Reply | Report Abuse | Link to thisDefine six custom moves as follows:
Z1 = mim10
Z2 = m2im9
Z3 = m3im8
Z8 = m8im3
Z9 = m9im2
Z10 = m10im
Define two more custom moves as follows:
Shift = Z3 I Z3 I Z10
Solve = Z9 Z10 I Z3 I Z3 Z8 I Z8
The first three moves, Z1, Z2, & Z3 all respect the "Triplets" (successive groups of three numbers). Z1 & Z2 exchange the Triplets in different ways, and Z3 rearranges the numbers within each Triplet.
Starting with 1 2 3 4 5 6... the sequence Z3 I gives 3 1 2 6 4 5...
Repeating Z3 I gives 2 3 1 5 6 4...
And repeating Z3 I once more restores 1 2 3 4 5 6...
The second three moves, Z8, Z9, & Z10 all respect the "Tetrads" (successive groups of four numbers). Z9 & Z10 rearrange the numbers within each Tetrad in different ways, and Z8 exchanges the Tetrads.
Starting with 1 2 3 4 5 6... the sequence Z8 I gives 9 10 11 12 4 3 2 1 8 7 6 5
Repeating Z8 I gives 8 7 6 5 12 11 10 9 1 2 3 4
And repeating Z8 I once more restores 1 2 3 4 5 6...
An interesting combination is Z8 I Z8 Z9 Z10 which gives 1 2 3 4 12 11 10 9 8 7 6 5
To solve the Puzzle, first get the numbers 1 through 6 (the "low numbers") all in the first six positions, then get them into the correct sequence. Use only the custom moves above, plus "I".
Starting from any random state, one of the Triplets will always have at least two low numbers. Move this to the first position with moves Z1 and Z2. If the second Tetrad does not contain any low numbers, use Z8 I Z8 and then it will.
Use Z3 I once or twice so that positions 1 & 2 are both low. Next goal is to get low numbers in positions 1, 2, & 3. If there is a low number in position 4, use Z10. If there is a low number in position 5 or 6, use Z3 I once or twice to move it to position 4, then use Z9 and Z10 as needed. If there is a low number in position 8, use Z10 to move it to position 7. If there is a low number in position 7, use Z3 I Z9 Z10 Z3 I Z3 I Z10.
Now be sure the second Tetrad still contains a low number. If not, use Z8 I Z8 and it will.
The next goal is to get low numbers in positions 1, 2, 3, & 4. If there is a low number in position 5 or 6, use Z3 I once or twice to move it to position 4. If there is a low number in position 7, use Z3 I to move it to position 8. If there is a low number in position 8, use Z9 Z3 I Z10 Z3 I.
Again be sure the second Tetrad still contains a low number. If not, use Z8 I Z8 and it will. Then use Z9 and Z10 to move that low number to position 5. Now positions 1, 2, 3, 4, and 5 are all low.
The remaining low number will be in position 6, 7, 8, 9, 10, or 11 (never 12). If it is in position 6, we are set. For position 7, 9, or 10 use "Shift" until it is in position 11. For position 11, use "Solve" twice, and all six low numbers will be on the left half of the puzzle. For position 8, use "solve" twice, then Z9 Z10 Z3 I Z3 I Z9, then use "solve" twice.
For the second half of the puzzle, we need to produce one triplet containing 1, 2, and 3. Typically two of these will be together in a triplet, and the third will need to be exchanged with one of the numbers in the other triplet. See which numbers need to be exchanged. Use Z3 I once or twice so these numbers are either together (in positions 3 & 4) or apart (in positions 1 & 6). If apart, use Z2 and they will be together. If together, use Z10 and the triplets will be defined (1, 2, & 3 in the same triplet).
If the numbers to be exchanged are in the same positions within their respective triplets (both first, both second, or both third in their own triplets), this technique will not work. If they are both second, use Z3 I. Then in any case use Z10, and the triplets can then be solved by using the previous paragraph on the new arrangement.
Once a triplet contains 1, 2, & 3 we are nearly done. Use Z3 I once or twice until the sequence is either 1, 2, 3 in order or 3, 2, 1 in order. If 3, 2, 1, use "Invert", then Z1.
If the puzzle is not yet solved, use Z2.
The End.
Seems, that my moves posted here
Reply | Report Abuse | Link to thishttp://www.sudoku.com/boards/viewtopic.php?p=58484#58484
are shorter.
Y1=IMIM3IM2IM9IM7IM8=(1)(2)(3)(4,7,6,12)(5,10,8,9)
Reply | Report Abuse | Link to thisY2=IM3IM6IMIM9IM7IM8=(1)(2)(3)(4,7)(5,6)(8,12)(9,11)
Y1=IMIM3IM2IM9IM7IM8=(1)(2)(3)(4,7,6,12)(5,10,8,9)
Reply | Report Abuse | Link to thisY2=IM3IM6IMIM9IM7IM8=(1)(2)(3)(4,7)(5,6)(8,12)(9,11).
We can simplify Y1,Y2,Z1,Z2 like this Y1=IM3IMIM3IMIM2IM3,Y2=MIMIMIM4IM2IMIMIM6IM,Z1=M3IM2IM5IM,Z2=MIM3IM2IM3IM5I.
Reply | Report Abuse | Link to thisZ1=M3/M2/M5/M=(1)(2)(3)(4)(5,10,12,7)(6,8,11,9).
Reply | Report Abuse | Link to thisZ2=M6/M3/M6/M4=(1)(2)(3)(4)(5,6,12,11)(7,8,10,9).
An interesting coincidence: I first read this article this afternoon. This evening my wife and I chose, as our evening's entertainment, a rewatching of the movie 'Memento'. As I was viewing the film it occurred to me that the system which the director uses [ to convert the chronological sequence of events into the order in which they are shown in the film ] is, with a little tweaking, very much like the Merge move in the M12 puzzle.
Reply | Report Abuse | Link to thisIsn't it true that we can get all transformations with composite permutations
Reply | Report Abuse | Link to thisIsn't it true that we can get all transformations by compositing permutations
Reply | Report Abuse | Link to thisWHERE
Reply | Report Abuse | Link to thisIMIM3IM2
Reply | Report Abuse | Link to thisIM2IM5IM4
IM3IM6IM
IM4IM2IM5
IM5IM8IM7
IM6IM9IM7
IM7IMIM5
IM8IM10IM6
IM9IM7IM8
IM10IM4IM7
are sequences which let (1,2)stay!
Keep trying!
IMIM3IM2
Reply | Report Abuse | Link to thisIM2IM5IM4
IM3IM6IM
IM4IM2IM5
IM5IM8IM7
IM6IM9IM7
IM7IMIM5
IM8IM10IM6
IM9IM7IM8
IM10IM4IM7
are sequences which let (1,2)stay!
Keep trying!
DEFINE:
Reply | Report Abuse | Link to thisX1=IMIM3IM2=(1)(2)(3,11,10.5,8,7,12,6)
X2=IM2IM5IM4=(1)(2)(8)(9)(3,10,4,5)(6,7,11,12)
X3=IM3IM6IM=(1)(2)(3,11,7,6,4,9,10,8)(5,12)
X4=IM4IM2IM5=(1)(2)(11)(12)(3,4,7,8)(5,6,9,10)
X5=IM5IM8IM7=(1)(2)(7)(10)(3,6,4,9)(5,8,12,11)
X6=IM6IM9IM7=(1)(2)(11)(12)(3,4,7,8)(5,6,9,10)
X7=IM7IMIM5=(1)(2)(3,9,5,4,8,10,11,12)(6,7)
X8=IM8IM10IM6=(1)(2)(3,9,5,4,8,10,11,12)(6,7)
X9=IM9IM7IM8=(1)(2)(3,12,6,4,5,8,10,11)(7,9)
X10=IM10IM4IM7=(1)(2)(3,10,9,7,4,12,8,5)
then:
Y1=X1X9
Y2=X7X5
Y3=X9X7=Z1
a solution unfinished.
First of all, I want to apologize for two things:
Reply | Report Abuse | Link to this(1)As my computer runs so slowly , I often thought of my comments as missed , consequently , I sent my comments twice sometimes .
(2)Yesterday, I called it "a new solution ." Actually, it's a more complete version of the original solution.
Then, I want to announce a new way to solve the M12 puzzle.
For the first thing :Define:
X2,1=IMIM3IM2=(1,3,2)=(1)(2)(3,11,105,8,7,12,6)
X2,2=IM2IM5IM4=(2,5,4)=(1)(2)(8)(9)(3,10,4,5)(6,7,11,12)
X2,3=IM3IM6IM=(3,6,1)=(1)(2)(3,11,7,6,4,9,10,8)(5,12)
X2,4=IM4IM2IM5=(4,2,5)=(1)(2)(11)(12)(3,4,7,8)(5,6,9,10)
X2,5=IM5IM8IM7=(5,8,7)=(1)(2)(7)(10)(3,6,4,9)(5,8,12,11)
X2,6=IM6IM9IM7=(6,9,7)=(1)(2)(11)(12)(3,4,7,8)(5,6,9,10)
X2,7=IM7IMIM5=(7,1,5)=(1)(2)(3,9,5,4,8,10,11,12)(6,7)
X2,8=IM8IM10IM6=(8,10,6)=(1)(2)(3,9,5,4,8,10,11,12)(6,7)
X2,9=IM9IM7IM8=(9,7,8)=(1)(2)(3,12,6,4,5,8,10,11)(7,9)
X2,10=IM10IM4IM7=(10,4,7)=(1)(2)(3,10,9,7,4,12,8,5)
X3,1=(1,3,7)=(1)(3)(4)(6)(2,10,11,12)(5,7,8,9)
X3,2=(3,6,6)=(1)(3)(4)(2,10,7)(5,8,6)(9,12,11)
X3,3=(4,2,9)=(1)(3)(2,8,10,6,1)(4,5,12,9,7)
X3,4=(5,8,2)=(1)(3)(2,6,9,11,4,7,8,10)(5,12)
X3,5=(7,1,3)=(1)(3)(10)(12)(2,7,8,9)(4,5,6,11)
X3,6=(8,10,4)=X3,5
X3,7=(9,7,10)=(1)(3)(2,5,6,12,4,8,11,9)(7,10)
X3,8=(10,2,3)=(1)(3)(2,11,5,4,6,9,10,12)(7,8)
,and xa,b means 1 and a stay
Y1=X2,1X2,9=(1)(2)(3)(11)(4,7,6,12)(5,10,8,9)
Y2=X2,7X2,5=(1)(2)(3)(11)(4,12,6,7)(5,9,8,10)
Y3=X2,9X2,7=(1)(2)(3)(4)(5,10,12,7)(6,8,11,9)
Y4=X3,1X3,4=(1)(2)(3)(4,7,10)(5,8,11)(6,9,12)
Y5=X3,2X3,4=(1)(2)(3)(11)(4,7,6,12)(5,10,8,9)
Y6=X3,5X3,2=(1)(2)(3)(5)(4,8,12,11)(6,9,10,7)
Y7=X3,4X3,7X3,1=(1)(2)(3)(8)(4,11,9,5)(6,10,7,12)
Y8=X3,4X3,7X3,8=(1)(2)(3)(8)(4,12,9,10)(5,6,11,7)
Z1=Y3
Z2=Y7Y6=(1)(2)(3)(4)(5,8,12,9)(6,7,11,10)
Z3=Y8Y5=(1)(2)(3)(4)(5,12)(6,11)(7,10)(8,9)
Z4=Y4Y2=(1)(2)(3)(4)(5,10,12,7)(6,8,11,9)
It's a advanced version of the original solution.
Then it will be very helpful to me to figure out a combination of I,M that composes (1,2,3,4,5,6,7,8,9,10,11,12).
Thank you!
I found that (1,2,3,4,5,6,7,8,9,10,11,12) is equevalent with
Reply | Report Abuse | Link to thisM10(1,3,5,7,9,11,12,10,8,6,4,2)M.
But i can only get(1,3,5,7,8,6,4,2)(9,10,11,12).