Rubik’s Cube and GAP

Rubik’s Cube
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.

Leave a Reply

You must be logged in to post a comment.