Scientific American: Simple Groups at Play

Everything about Sudoku that doesn't fit in one of the other sections

Scientific American: Simple Groups at Play

Postby submacrolize » Tue Jun 24, 2008 5:11 am

Read the article here, and play the puzzles here.

The puzzles are interesting and quite challenging. At the moment I'm working on M12. Any ideas for a general solution?
submacrolize
 
Posts: 12
Joined: 27 February 2008

Postby Luke » Tue Jun 24, 2008 5:34 am

Withdrawn.
Last edited by Luke on Tue Jun 24, 2008 10:21 am, edited 1 time in total.
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby eleven » Tue Jun 24, 2008 8:40 am

You can view the solution here:
Code: Select all
1 2 3 4 5 6 7 8 9 10 11 12
eleven
 
Posts: 1559
Joined: 10 February 2008

Postby Glyn » Tue Jun 24, 2008 11:57 am

An interesting puzzle which unfortunately will be overlooked because of the identity of the original poster. submacrolize I hope you have now realized that giving people the solutions alone means you will not get taken seriously and will refrain from chipping in with them continually.

Concerning the M12 puzzle. The repeated Merge/Invert operations so far posted on the Sciam page effectively act as a 'do nothing' operator. Merge 11 times does the same. No one has yet posted the transformations required to take a particular randomized sequence to the ordered sequence.
Glyn
 
Posts: 357
Joined: 26 April 2007

Postby Mauricio » Tue Jun 24, 2008 8:08 pm

eleven wrote:You can view the solution here:
Code: Select all
1 2 3 4 5 6 7 8 9 10 11 12

:D
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby eleven » Wed Jun 25, 2008 8:17 am

This should work:
Its easy to place 1 and 2 to positions 1 and 2. Then
3 to pos 3: IMIM3IM2
4 to pos 4: M3IMIM3IM5 (from pos 8,9), IMIMIM2IMIM2IMIM (from pos 5, 12)
5 to pos 5: M3IM2IM5IM (from pos 7, 10, 12), MIM3IM2IM3IM5I (from pos 6, 11, 12)
If 4 or 5 are in other positions, use one move to bring it in position for the other.
eleven
 
Posts: 1559
Joined: 10 February 2008

Postby udosuk » Wed Jun 25, 2008 8:55 am

You can find a workable program/algorithm in here:

http://www.hakank.org/minizinc/M12.mzn

The author, Hakan Kjellerstrand, also wrote heaps of programs for other well known puzzles/problems in his home page:

http://www.hakank.org/minizinc

This website has nothing to do with me, but I guess it's better than submacrolize's spamming of Sudoku solutions.:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby eleven » Wed Jun 25, 2008 9:16 am

Its not very helpful for me to see cryptic code in an exotic programming language. Can you explain, what it does ?
eleven
 
Posts: 1559
Joined: 10 February 2008

Postby Glyn » Wed Jun 25, 2008 11:32 am

Excellent work eleven:)

This hopefully explains eleven's moves in more detail.

Its easy to place 1 and 2 to positions 1 and 2.
Merge until 1 is in Position 12 Then invert.
Merge until 2 is in Position 2.

3 to pos 3: leaving positions 1 and 2 unchanged
IMIM3IM2 takes position 3 through the cycle of positions {3,11,10,5,8,7,12,6,3}
(if 3 is in positions 4 or 9 it needs to be moved eg to position 8 using a move for position 4).
4 to pos 4: leaving positions 1,2 and 3 unchanged
M3IMIM3IM5 takes position 4 through the cycle of positions {4,9,8,4}
IMIMIM2IMIM2IMIM takes position 4 through the cycle of positions {4,12,5,4}
(if 4 is in positions 6,7,10,11 use moves for position 3 or 5 to move it first)
5 to pos 5: leaving positions 1,2,3 and 4 unchanged
M3IM2IM5IM takes position 5 through the cycle {5,10,12,7,5}
MIM3IM2IM3IM5I takes position 5 through the cycle {5,9,8,6,5}
(if 5 is in position 11 use a move for position 3 to shift it first)

Hope this is useful.
Glyn
 
Posts: 357
Joined: 26 April 2007

Postby eleven » Wed Jun 25, 2008 3:09 pm

Thanks Glyn.

At the second glance one of the 3rd and 4th move is not needed. The cycles of the moves are:

Code: Select all
1.IMIM3IM2 :         (1),(2),(3.6.12.7.8.5.10,11),(4,9)

2.M3IMIM3IM5 :       (1),(2),(3),(4,8,9),(5,6,10),(7,11,12)
3.IMIMIM2IMIM2IMIM : (1),(2),(3),(4,5,12),(6,7,8),(9,10,11)

4.M3IM2IM5IM:        (1),(2),(3),(4),(5,7,12,10),(6,9,11,8)
5.MIM3IM2IM3IM5I:    (1),(2),(3),(4),(5,6,12,11),(7,8,10,9)

As Glyn pointed out, if the 3 is in position 4 or 9, you can use move 3 to bring it to pos 8 and (4 times) move 1 to pos 3.

Move 2 brings 4 to pos 4 from pos 9 or 8 (2 times).
If its not there, but in (5,6,10), first bring it to 6 (if necessary) by move 2, then to 9 by move 4 and to 4 by move 2 again.
If its in (7,11,12), bring it to 11 (move 2), then to 8 by move 4, then 2 times move 2 for pos 4.

Move 4 brings 5 to pos 5 from 7,12 and 10.
If its in (6,9,11,8), use move 4, until its in 6, then 3 times move 5 to pos 5.
eleven
 
Posts: 1559
Joined: 10 February 2008

Postby udosuk » Wed Jun 25, 2008 4:09 pm

eleven wrote:Its not very helpful for me to see cryptic code in an exotic programming language. Can you explain, what it does ?

I suppose it uses a brute-force approach to work out a solution to solve a M12 puzzle. For most of us it shouldn't be much helpful. But for submacrolize it should be as all he cares is the solution.:D

BTW nice scheme eleven. Let me guess - you're also a great Rubik's cube solver? Have you tackled the "Professor's Cube"?
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby wintder » Wed Jun 25, 2008 4:14 pm

Is it just me who gets 403 errors trying the link?
wintder
 
Posts: 297
Joined: 24 April 2007

Postby Glyn » Wed Jun 25, 2008 5:01 pm

I think it must be just you having a problem with the link. Try approaching it from the Scientific American's main web page. Then select Magazine.

If you try the M24 puzzle note that you have to drag the numbers not enter L,R and S in Move History. The letters only work when assembling custom moves.

Matt I think that submacrolize has seen the error of his ways, but we will have to wait and see.

There are quite a few assemblies which achieve similar results. I guess the next task is to find the minimum set of I and M to achieve reordering. eg for moving the 3 (given 1 and 2 correct) we can use eleven's IMIM3IM2 or something else such as IM3IM6IM which reaches the parts the other one doesn't (but not all) and moves the 3 quicker from certain starting points.

Of course there is no reason to place 1 and 2 first anyway if a minimum set is required.
Glyn
 
Posts: 357
Joined: 26 April 2007

Postby eleven » Fri Jun 27, 2008 8:57 am

udosuk wrote:BTW nice scheme eleven. Let me guess - you're also a great Rubik's cube solver? Have you tackled the "Professor's Cube"?
Thanks.
I was crazy enough to bet, that i could do it in 3 days. When i thought, i finally got it on the 3rd day, i realized, that i needed a 3rd move for the corners (plus the one for the edges and one for the middle stones). So it became a long day too to repair it.
I did not bet again:)
eleven
 
Posts: 1559
Joined: 10 February 2008


Return to General