    -- Copyright (c) David Amos, 2009. All rights reserved.

    module Math.Projects.Rubik where

    import Math.Algebra.Group.PermutationGroup hiding (_D)
    import Math.Algebra.Group.SchreierSims as SS
    import Math.Algebra.Group.RandomSchreierSims as RSS
    import Math.Algebra.Group.Subquotients

    -- Rubik's cube

    --           11 12 13
    --           14  U 16
    --           17 18 19
    -- 21 22 23   1  2  3  41 42 43  51 52 53
    -- 24  L 26   4  F  6  44  R 46  54  B 56
    -- 27 28 29   7  8  9  47 48 49  57 58 59
    --           31 32 33
    --           34  D 36
    --           37 38 39

    f = p [[ 1, 3, 9, 7],[ 2, 6, 8, 4],[17,41,33,29],[18,44,32,26],[19,47,31,23]]
    b = p [[51,53,59,57],[52,56,58,54],[11,27,39,43],[12,24,38,46],[13,21,37,49]]
    l = p [[21,23,29,27],[22,26,28,24],[ 1,31,59,11],[ 4,34,56,14],[ 7,37,53,17]]
    r = p [[41,43,49,47],[42,46,48,44],[ 3,13,57,33],[ 6,16,54,36],[ 9,19,51,39]]
    u = p [[11,13,19,17],[12,16,18,14],[ 1,21,51,41],[ 2,22,52,42],[ 3,23,53,43]]
    d = p [[31,33,39,37],[32,36,38,34],[ 7,47,57,27],[ 8,48,58,28],[ 9,49,59,29]]

    rubikCube = [f,b,l,r,u,d]
    -- In Singmaster notation these would be capital letters.

    [cornerFaces,edgeFaces] = orbits rubikCube

    (kerCornerFaces,imCornerFaces) = transitiveConstituentHomomorphism rubikCube cornerFaces
    -- kernel is the elts which fix all corner faces
    -- image is the action restricted to the corner faces

    (kerEdgeFaces,imEdgeFaces) = transitiveConstituentHomomorphism rubikCube edgeFaces
    -- kernel is the elts which fix all edge faces
    -- image is the action restricted to the edge faces

    [cornerBlocks] = blockSystems imCornerFaces
    [edgeBlocks] = blockSystems imEdgeFaces

    (kerCornerBlocks,imCornerBlocks) = blockHomomorphism imCornerFaces cornerBlocks
    -- kernel is elts which fix all the corners as blocks, with order 3^7
    -- (Whenever you twist one corner you must untwist another
    -- - so the action on 7 corners determines the 8th)
    -- image is the action on the corners as blocks, which is S8 of order 20160

    (kerEdgeBlocks,imEdgeBlocks) = blockHomomorphism imEdgeFaces edgeBlocks
    -- kernel is elts which fix all the edges as blocks, with order 2^11
    -- (Whenever you flip one edge, you must flip another edge
    -- - so the action on 11 edges determines the 12th)
    -- image is the action on the edges as blocks, which is S12 of order 479001600

    -- Note that orderSGS imCornerFaces * orderSGS imEdgeFaces == 2 * orderSGS (sgs rubikCube)
    -- This is because you can't operate on corners and edges totally independently
    -- If you swap two corners, you must also swap two edges

    -- See also
    -- http://www.gap-system.org/Doc/Examples/rubik.html

    -- (Note that the kernel of the corner constituent homomorphism /= image of edge constituent homomorphism
    -- For example, [[36,38],[48,58]] is in the latter, but not the former because it's not in the Rubik group
    -- ie there is an elt in the Rubik group which does just that to the edges, but may do some things to the corners)

    -- Rubik's revenge (4*4*4 cube)

    --                    1   2   3   4
    --                    5   6   7   8
    --                    9  10  11  12
    --                   13  14  15  16
    -- 101 102 103 104  201 202 203 204  301 302 303 304  401 402 403 404
    -- 105 106 107 108  205 206 207 208  305 306 307 308  405 406 407 408
    -- 109 110 111 112  209 210 211 212  309 310 311 312  409 410 411 412
    -- 113 114 115 116  213 214 215 216  313 314 315 316  413 414 415 416
    --                  501 502 503 504
    --                  505 506 507 508
    --                  509 510 511 512
    --                  513 514 515 516

    _U = p [[1,13,16,4],[2,9,15,8],[3,5,14,12],[6,10,11,7],
            [101,201,301,401],[102,202,302,402],[103,203,303,403],[104,204,304,404]]
    _u = p [[105,205,305,405],[106,206,306,406],[107,207,307,407],[108,208,308,408]]
    _d = p [[109,209,309,409],[110,210,310,410],[111,211,311,411],[112,212,312,412]]
    _D = p [[113,213,313,413],[114,214,314,414],[115,215,315,415],[116,216,316,416],
            [501,504,516,513],[502,508,515,509],[503,512,514,505],[506,507,511,510]]

    bf = p [[1,304,516,113],[2,308,515,109],[3,312,514,105],[4,316,513,101],
            [5,303,512,114],[6,307,511,110],[7,311,510,106],[8,315,509,102],
            [9,302,508,115],[10,306,507,111],[11,310,506,107],[12,314,505,103],
            [13,301,504,116],[14,305,503,112],[15,309,502,108],[16,313,501,104],
            [201,204,216,213],[202,208,215,209],[203,212,214,205],[206,207,211,210],
            [401,413,416,404],[402,409,415,408],[403,405,414,412],[406,410,411,407]]

    _R = _U ~^ bf
    _r = _u ~^ bf
    _l = _d ~^ bf
    _L = _D ~^ bf

    ud = _U * _u * _d * _D

    _B = _R ~^ ud
    _b = _r ~^ ud
    _f = _l ~^ ud
    _F = _L ~^ ud

    -- Note that orderSGS $ sgs [_U,_u,_d,_D,bf] comes out much too large,
    -- because it includes rotations of the whole cube (24)
    -- and exchanges of indistinguishable centre faces (24 for each of 6 colours)
    -- So we have to divide by 24^7 / 2.
    -- (The /2 is because we can only have even permutations when exchanging indistinguishable centres)