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