Blag

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.

This entry was posted on Mittwoch, Juli 1st, 2009 at 18:21 and is filed under conference, puzzle, RISC Summer. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.