The afternoon lecture by Alexander Konovalov was a huge fun. Aside from all the algebraical goodness in GAP, he demonstrated something really amazing even to generic audience. It is actually easy to represent Rubik’s Cube as a group.
Let’s just unfold the cube and number the faces.
+--------------+ | | | 1 2 3 | | | | 4 top 5 | | | | 6 7 8 | | | +--------------+--------------+--------------+--------------+ | | | | | | 9 10 11 | 17 18 19 | 25 26 27 | 33 34 35 | | | | | | | 12 left 13 | 20 front 21 | 28 right 29 | 36 rear 37 | | | | | | | 14 15 16 | 22 23 24 | 30 31 32 | 38 39 40 | | | | | | +--------------+--------------+--------------+--------------+ | | | 41 42 43 | | | | 44 bottom 45 | | | | 46 47 48 | | | +--------------+
Then you can represent the cube as
gap> cube := Group( > ( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19), > ( 9,11,16,14)(10,13,15,12)( 1,17,41,40)( 4,20,44,37)( 6,22,46,35), > (17,19,24,22)(18,21,23,20)( 6,25,43,16)( 7,28,42,13)( 8,30,41,11), > (25,27,32,30)(26,29,31,28)( 3,38,43,19)( 5,36,45,21)( 8,33,48,24), > (33,35,40,38)(34,37,39,36)( 3, 9,46,32)( 2,12,47,29)( 1,14,48,27), > (41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40) );
GAP can tell you, how many different positions the puzzle has:
gap> Size( cube ); 43252003274489856000
And that’s pretty damn much. But the best is: you can actually produce a solution from an arbitrary position just in three lines of GAP code. It looks like this:
Initial state of the cube : ( 1,38,24,11, 3,16,40, 8)( 2,20, 5,18,31,34,13,26, 7,45)( 4,12,47,36,23,21,10, 37,39,29,42,28)( 6,33,22,14,25, 9,48,30)(17,27,41,46,19,35,32,43) Solution of the cube : L^-1*T^-1*B^-1*T^2*B*L*F*R*T^-1*R^-1*F^-1*T*F*R*T*R^-1*T^-1*F^-1*T*L*T*L^-1*F^ -1*L*T^-1*L^-1*T*F*T^3*L^-1*T^-1*B*L^-1*B^-1*L*T*L^2*F*T*F^-1*T^-1*L^-2*T*L*F^ -1*L*F*L^-1*T^-1*L^-1*F^-1*L^-2*F*L^2*T*B^-1*T^-1*B*L^-1*D*F^-2*D^-1*F^-1*T*L^ -1*F*T^-1*F*L^-1*D*R*D^-1*B^-1*R^-1*B*T*R*F^-1*B*T^-1*B^-1*R^-1*T*D^-1*R^-1
… and we shall look into how we get it.
First, let us define the legitimate movements.
f:=FreeGroup("T","L","F","R","B","D");
Secondly, we define
hom:=GroupHomomorphismByImagesNC( f,
cube,
GeneratorsOfGroup( f ),
GeneratorsOfGroup( cube ) );
(and it’s just one line in GAP. ;))
And now we can apply it.
# define some state of the cube
x := Random( cube );
# print the sollution for this state
PreImagesRepresentative( hom, x );
That’s it folks!
A more in-depth reading is the actual example of Rubik’s Cube in GAP. Oh, and the image at the beginning of this text is from here.