-- 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)