You didn't think I had any particular reason for rambling about the Rubik's Cube? I started talking about it because in the recent issue of Scientific American, there is a very interesting article about the Rubik's Cube and similar puzzles. Sorry, it's subscription only, but I'll explain the basic ideas.
Permutation puzzles, as I previously explained, are puzzles where you have to arrange a number of items (like cubies or numbers) into the correct order. The underlying mathematics of permutation puzzles is called Group Theory. That's right, you're doing advanced mathematics when you turn a Rubik's Cube! Basically, all the possible positions of a permutation puzzle constitute a "group". For a Rubik's Cube, the size of this group is 43,252,003,274,489,856,000. But don't be intimidated by the size. As I said, the vast majority of permutation puzzles are easy. I mean, sure, you've got a 4-dimensional Rubik's Cube that boggles the mind, but they're easy in principle.
The mathematical reason that most permutation puzzles are easy is because they are based on symmetric or alternating groups. In a symmetric group, every single permutation is possible. In an alternating group, half of the permutations are possible. Maybe the previous three sentences made no sense to you, so allow me to translate to a concrete example: the Rubik's Cube. If the Rubik's cube is based on a symmetric group, that means you can find a way to switch two cubies without changing anything else. If it is based on an alternating group, that means you can find a way to switch three cubies without changing anything else.
But what happens if you've got a puzzle based on a much more complicated group? What if the simplest algorithm possible must switch 4 cubies at a time, or more? If we look to the mathematical research, there are lots of different finite simple groups. There are exactly 16 families of groups, plus 27 oddball groups, called the sporadic groups. (What's really amazing to me is that mathematicians can prove that there are no other finite simple groups.) So what happens if we build a puzzle based on one of those sporadic groups?
Well, that's what the Scientific American article did. They built puzzles based on the M12 sporadic group, the M24 sporadic group, and the Co0 group (aka the dotto group). Try them yourself!
The M24 puzzle and the dotto puzzle look ridiculously complicated, and I don't, at the moment, have enough patience to solve them. But let's look at the M12 puzzle.
Basically, you've got two moves called Invert and Merge. You can also create a custom macro, if you ever find an algorithm that you like. To solve this puzzle, I followed the same basic steps as I explained for the Rubik's cube. However, they are no longer easy. It is impossible to find an algorithm that switches exactly 2 or 3 numbers. In fact, you must switch at least 8 numbers at a time! Nevertheless, I came up with some useful algorithms.
So do you want some tips on solving the M12 puzzle? Try these simple algorithms. I came up with cryptic names for them too!
2-invert: MIM10I
2-bike: M2IM9
6-bike: M10IM
4-trike: M3IM8I
3-bike: M9IM2
bike/invert: M8IM3
Once you figure out what they do, you'll have to come up with a super-algorithm that combines them to solve the puzzle. It isn't easy, even with my hints.
Monday, June 30, 2008
Subscribe to:
Post Comments (Atom)
24 comments:
Do you mean to say that these six moves are sufficient to solve the puzzle? It would be interesting to see how you do that, or at least give some pointers in the right direction.
Yes, the six combos I give are sufficient to solve the puzzle, if perhaps not in the most efficient way.
My general strategy was to first get 1 through 6 on the left side and then move them into the correct permutation with the 2-bike, 4-bike, 6-bike, and 2-invert. Once the first six are correct, the last six are forced into the correct positions.
OK, here's a challenge for you. Initial Position 4 2 3 1 6 5 10 8 9 7 12 11.
This has numbers 1 thru 6 on the left side. Can you solve it (or produce it) using your limited moves? It looks to me that this position is OUTSIDE of the sub-group reachable by those moves.
On second thought, you can delete my last post. Problem solved to this point.
Using these successive positions:
423-165-xxx-xxx
241-356
412-563
563-412
654-321
123-456
Each is reachable by the limited moves (and "invert").
So how many moves does your solution need in typical cases or the worst case?
The tack I took was rather different -- and, contrary to what Katz and Siegel say, it IS similar to what one does in solving Rubik's Cube (or at least what I do) -- specifically the first steps in solving the cube, when I solve a single layer by putting one cubie at a time into place, leaving the rest of that layer undisturbed but not worrying about what it does to the the other two layers. The difference is, with M12, when you put the fifth "cubie" into place, the rest fall into line automatically.
My worst case solution length is 77 moves, which is admittedly a lot larger than the lower limit of 22 I get for the worst case solution length of God's Algorithm.
How many moves does it take? I haven't even considered that aspect. I always thought that the problem of minimizing the number of moves (finding god's algorithm) was so difficult as to be inaccessible to lay mathematicians. Am I wrong? Is it easier than I thought?
IM2IM5IM4
IMIM3IM2
IMIM3IM2IM9IM7IM8
IM3IM6IMIM9IM7IM8
IM9IM7IM8IM7IMIM5
IMIM3IM2IM7IMIM5IM7IMIM5
these moves are sufficient
I'm afraid those moves won't get you anywhere unless 1 and 2 are already in the correct positions.
In any case, we could just take "I" and "M" as sufficient moves--the trouble is that it's not obvious how to use them by themselves.
"How many moves does it take? I haven't even considered that aspect."
Any normalized position (positions with numbers one and two in their correct positions) can be solved (or produced) in no more than 28 moves. One such "longest move" is m2-i-m3-i-m3-i-m-i-
m-i-m4-i-m2-i-m-i-m3
which solves the position 1,2,9,11,12 to Normal, and produces the position 1,2,6,8,12 from Normal. I don't think this transform has much chance of being made any shorter.
I also had a lot of fun with M12 when I came across it in the Scientific American article. I wrote my own version of the M12 puzzle that can solve it. It does so by having an exhaustive database of all positions (nothing clever).
As to the worst case scenario - there are several positions that are 29 moves from being solved, but none that are 30.
to selliott4:
Your site http://selliott.org/puzzles/m12
cannot be opened
I clicked on the link from selliott4 and it worked fine for me...http://selliott.org/puzzles/m12.
I have worked on the m24 and have some results. Are there other solutions on internet?
I haven't seen any (and was unable to figure out anything myself). If you've got a solution to the M24, or even part of a solution, you should put them up on the internet. You'll definitely get an audience for that.
Solution for M24
- Bring home 0
- Bring home 15
- The operator h has two cycles of length 11
c1=(1 21 5 9 17 22 4 10 20 2 19) and
c2=(3 11 16 6 8 13 12 14 7 18 23)
If the actual place of 16 is in c1 apply h immediately to bring 16 home
else use operator a to get 16 in c1
- R
- The operator a has 4 cycles of length 5
d1=(1 23 6 14 11)
d2=(2 3 18 8 13)
d3=(4 20 5 21 7) and
d4=(9 19 22 12 10)
If the actual place of 17 is in d2 apply a immediately to bring 17 at 18
else use operator w to get 17 in d2
- L
- Note the cycles C still necessary to solve the puzzle
- Find theses cycles in the ordered table of 957 aw-combinations
(should be 960 = 48*20)
- If you cannot find a combination try also the inverted C
- If you still cannot find a combination apply first some a and note again the cycles C
- Apply the found aw-combination
If you had inverted C than you must apply the combination m times where
m is the length of cycles in C minus 1
Tools
h is R9SLSL11SR5SR6SRSL9 and yields
(0) (15) (1 21 5 9 17 22 4 10 20 2 19) (3 11 16 6 8 13 12 14 7 18 23)
a is SR2SL11SR2SR7SR2SL2SR2SL2SR2SL2SR2SL2 and yields
(0) (15) (16) (17) (1 23 6 14 11) (2 3 18 8 13) (4 20 5 21 7) (9 19 22 12 10)
w is RSR2SL11SR2SR7SR2SL2SR2SL2SR2SL2SR2SL2SR2SL11SR2SR7SR2S
L2SR2SL2SR2SL2SR2SL2SR2SL11SR2SR7SR2SL2SR2SL2SR2SL2SR2SL2SR2
SL11SR2SR7SR2SL2SR2SL2SR2SL2SR2SL5SR5SL5SR5SL5SR5SL5SR5SL5SR5
SL5SR5SL5SR5SL5SR5SL11SR11SL5SR5SL5SR5SL2SR2SL11SR2SR7SR2SL2
SR2SL2SR2SL2SR2SL3 and yields
(0) (15) (16) (17) (1 22 19 3 6) (2 13 5 4 9) (7 11 8 23 18) (10 20 12 21 14)
w was constructed so that it has the same fixed elements as a
The aw-table is
wwaawwaa ( 1 ) ( 2 ) ( 3 10 ) ( 4 23 ) ( 5 8 ) ( 6 9 ) ( 7 ) ( 11 21 ) ( 12 ) ( 13 22 ) ( 14 19 ) ( 18 20 )
aaawwaaawa ( 1 ) ( 2 ) ( 3 11 ) ( 4 22 ) ( 5 6 ) ( 7 ) ( 8 9 ) ( 10 21 ) ( 12 ) ( 13 23 ) ( 14 20 ) ( 18 19 )
...
wwaaaa ( 1 9 8 3 11 ) ( 2 20 5 10 22 ) ( 4 13 7 18 14 ) ( 6 19 23 21 12 )
This table has been constructed by a programm using only the cycles of a and w.
That's great! The only thing that's missing is the rest of the aw-table. Do you have the rest on your webpage somewhere?
I have put the m24 aw-table on my homepage private.mcnet.ch/baumann
These "tools" for M24 can be shortened.
h is L8SL5SL5SR10SL5
a is SR2SR12SR2SR9SL2S
w is SR5SR12SR3SR7SR13SR2
All positions in M24 can be solved using no more than eleven "S" moves (and the proper L & R in between!).
Wow, how do you all know all this? Do you study group theory?
When you mentioned yesterday that you had not yet seen a solution for the M24 Puzzle, I decided to solve it. I hacked together a computer program that can produce or solve any position in the Puzzle. So I looked at those long Transforms posted by M. Baumann and converted them into positions (applying the Transform to the solved state), then used my program to give the shortest transform to give the same result. (Shortest in terms of fewest "S" moves.) Also saw that 5 "S" moves suffice to give an example of a sequence beginning with any arbitrary five numbers. Also that the transform from any one of these to any of the 48 variants starting with the same five numbers can be done with no more than 6 "S" moves. So eleven "S" moves is proven to be sufficient, although it is likely that 7 (or perhaps 8) would actually suffice. Seven "S" moves appear to be required for some positions, because otherwise there would not be sufficient different moves to generate the full number of different positions.
The key to analyzing and programming both puzzles is to use a different way of visualizing the Group and the Puzzle. For M12, the Merge move leaves position 1 unchanged, and shifts everything else around a twisted eleven-cycle. After eleven merge moves, the original position returns. So all those merges never really go anywhere, they just run in circles around a "ring" containing those eleven related positions.
Of the 95040 positions in the M12 group, each is a member of exactly one of these 8640 Rings. The distinguishing feature on each ring would be the invariant number on position 1.
Let's sort the rings by that initial number, stacking them in twelve different piles and placing each pile on a little "Post" to hold them in place. Then each of the twelve Posts holds exactly 720 Rings.
To make a "Post move", the procedure is as follows. Say we want to move to Post 2... then perform "merge" repeatedly until the number 2 lands in position 12, then Invert and the 2 is in position 1. We are now on Post 2.
The "Normalized" positions (those having number 1 in position 1 and number 2 in position 2) represent the "preferred" or reference position on each of the 720 Rings on Post 1. Each position on each Ring connects with a single position on a single Ring on another Post by way of an Invert move. So the intricate interlacing of the Invert moves is what gives the puzzle all of its connectivity and complexity.
Taking collectively all of the Invert moves from all of the positions on all of the Rings on Post 1, they connect to a single position on each and every Ring on each of the other Posts.
In this way, every position in the Puzzle is accounted for. But each Ring on each post is connected via an Invert move to one ring on EACH other post. The total number of connections, or distinct Invert moves, is exactly 1/2 the total number of positions in the puzzle (since each position can be inverted, and since each Invert connects two positions).
To get from one normalized position to another, it is necessary to visit at least two other posts. From post 1, to any other post, then to any different post, then back to post 1. From each Ring on post 1, there are 66 other rings on post 1 that can be reached in this way (67 counting the position you start from). From each ring, 11 positions therefore 11 invert moves, and on each of those 11 rings reached, eleven positions... one by which we arrive, and 10 positions whose Invert will go somewhere else. Thus 110 rings in the second generation, each of which can Invert back to Post 1 (after the appropriate merge moves to get the 1 in position 12). But only 66 new positions reached on post 1, because many of the connections converge onto the same rings.
Doing this again, we might expect 66x66 new positions reached, but after convergence we find exactly 718 rings reached on post 1... all but two of the total. On the third try, these two are also reached and no part of the puzzle remains inaccessible.
So a computer program can just scan for all the possible Post moves and see which ones lead to positions of interest. Problem solved.
However, the Post moves do not work like transforms... they require a SPECIFIC starting sequence and a SPECIFIC ending sequence. Great for going between the solved state and any specific state of interest. To turn a post move into a transform, we just take note of exactly what sequence of merge and invert moves was involved. Such a sequence will always perform the same RELATIVE transformation on any position in the Puzzle.
Back to the M24 Puzzle, it all works the same way, but bigger. And instead of five numbers defining a position exactly, now the same five numbers just defines a Group of 48 related positions, which must be converted to one another by the appropriate transforms. Enjoy!
Try out this tool(S6)for
(23)(22)(21)(20)(19)(18)
R11SR9SR3
S5,S4,S3,and S2 are more complicated
but can they finish any M24 in less than a minute
There is now a really cool iPhone app that implements an M12 Sporadic Group puzzle. The group is presented like the M24 group, as a ring of 11 and a swap permutation. The app lets you pick one of 341 swap permuations that can generate the group, so you need different combos. It looks to me like there are only 31 really different swaps, though.
I think this link gets you to the app:
http://itunes.apple.com/us/app/sporadic-m12/id322438247
New URL. Baumanneduard.ch. instead of mcnet.ch/baumann
Post a Comment