为了简便,以 2 阶魔方为例。
我们将正方体的六个面展开如下:
其中俯视图、正视图、右侧视图分别为 我们称之为主面,它们的对面分别是 ,称之为次面。每个面都分成四个小方块:
例如,当 时,则此面为
当我们将 面逆时针旋转 ,我们只需要观察上层魔方的变化:
同理,关于侧视图、正视图也有类似的旋转。如果在复平面中,这种旋转的变换表示十分简洁:
所以不妨以 分别表示 的逆时针旋转(同时也可以看做是这三个面的外法向量)。另外,我们不需要考虑次面的旋转:若我们对 面进行旋转 ,再对 进行旋转 ( 的外法向量),则魔方恢复原状,从代数上也是很符合的:
表示恒等变换。所以旋转 的逆向操作即逆元,有两种等价的操作:或者将 顺时针旋转,或者将 进行逆时针旋转,我们都将此记成 。关于侧视图、正视图的旋转同理。
于是,我们考虑一个变换群:
这个群的乘法是变换的复合, 为生成元,词群()的关系() 比较复杂,比较显然的有: 将一个面朝同一方向旋转 4 次就会恢复原状。这个群我们称之为 阶魔方群。
至于逆元,由前文易得知。这个群显然是有限的,从置换群的角度看,魔方的状态是有限的,于是它是某置换群的子群。
回到题主的问题,魔方复原总是可解吗?已知当前魔方的状态,我们只要构造出它的逆元即可。求一个元素的逆元在群论中是非常容易的事情,例如 的逆元就是 。至于用某些公式(即特殊的关系),总可以使得魔方的状态进入一个轨道,这个轨道经过初始状态,于是只要按照公式机械重复操作,则其结果始终在此轨道上,并且最终到达目的地。理论上,我们可以把这个有限群以图论的方式表示:每个状态记为一个节点,如果存在一个变换,可以从此状态得到彼状态,那么这两个节点必有一条边相连接。于是,我们可以求任意节点到初始状态所代表节点的(最短)路径,这是图论中最基本的问题。
我再补充一下魔方群的关系:我们观察部分词()的阶,这些词我们按照代数式的次数进行分类。
声明:
于是我们任意给定一个 幂次乘积的有限序列,通过上面公式的可以化简为更简洁的序列。
####2阶魔方 #矩阵中心对称 o <- function(A) { t = A[1,1] A[1,1] = A[2,2] A[2,2] = t t = A[1,2] A[1,2] = A[2,1] A[2,1] = t A } #矩阵元素逆时针旋转 r <- function(A) { t = A[1,1] A[1,1] = A[1,2] A[1,2] = A[2,2] A[2,2] = A[2,1] A[2,1] = t A } #矩阵元素顺时针旋转 v <- function(A) { t = A[1,1] A[1,1] = A[2,1] A[2,1] = A[2,2] A[2,2] = A[1,2] A[1,2] = t A } #魔方的六个面 A = matrix(rep(1,4),2) B = matrix(rep(2,4),2) C = matrix(rep(3,4),2) a = matrix(rep(4,4),2) b = matrix(rep(5,4),2) c = matrix(rep(6,4),2) #A为俯视图,B为正视图,C为右侧视图,X=A,B,C;结果为矩阵形式,方便绘图。 Xup <- function(A,a,B,b,C,c) { Aup = matrix(rep(0,48),6) Aup[3:4,5:6] = A Aup[3:4,1:2] = a Aup[1:2,5:6] = B Aup[5:6,5:6] = b Aup[3:4,3:4] = C Aup[3:4,7:8] = c Aup } cube = list(A,a,B,b,C,c) cube[[7]] = Xup(A,a,B,b,C,c) #B朝上的十字架展开图(A --> B),输入输出皆为列表 ABup <- function(Aup) { Bup = list() Bup[[1]] = Aup[[1]] Bup[[2]] = o(Aup[[2]]) Bup[[3]] = Aup[[3]] Bup[[4]] = o(Aup[[4]]) Bup[[5]] = v(Aup[[5]]) Bup[[6]] = r(Aup[[6]]) Bup[[7]] = Xup(Bup[[3]],Bup[[4]],Bup[[2]], Bup[[1]],Bup[[5]],Bup[[6]]) Bup } #(B --> A) BAup <- function(Bup) { Aup = list() Aup[[1]] = Bup[[1]] Aup[[2]] = o(Bup[[2]]) Aup[[3]] = Bup[[3]] Aup[[4]] = o(Bup[[4]]) Aup[[5]] = r(Bup[[5]]) Aup[[6]] = v(Bup[[6]]) Aup[[7]] = Xup(Aup[[1]],Aup[[2]],Aup[[3]], Aup[[4]],Aup[[5]],Aup[[6]]) Aup } #C朝上的十字架展开图(A --> C) ACup <- function(Aup) { Cup = list() Cup[[1]] = Aup[[1]] Cup[[2]] = Aup[[2]] Cup[[3]] = r(Aup[[3]]) Cup[[4]] = v(Aup[[4]]) Cup[[5]] = Aup[[5]] Cup[[6]] = Aup[[6]] Cup[[7]] = Xup(Cup[[5]],Cup[[6]],Cup[[3]], Cup[[4]],Cup[[2]],Cup[[1]]) Cup } #(C --> A) CAup <- function(Cup) { Aup = list() Aup[[1]] = Cup[[1]] Aup[[2]] = Cup[[2]] Aup[[3]] = v(Cup[[3]]) Aup[[4]] = r(Cup[[4]]) Aup[[5]] = Cup[[5]] Aup[[6]] = Cup[[6]] Aup[[7]] = Xup(Aup[[1]],Aup[[2]],Aup[[3]], Aup[[4]],Aup[[5]],Aup[[6]]) Aup } #画出魔方展开图 color = c("white","red","orange","yellow","green","blue","purple") par(mai=rep(0,4),oma=rep(0,4)) plot(0,0, type = "n", xlim = c(0,7), ylim = c(0,9)) draw <- function(Cube) #输入矩阵 { for(i in 1:6)for(j in 1:8)points(i, j, pch = 15, cex = 4, col = color[Cube[i,j]+1]) } draw(Xup(A,a,B,b,C,c)) #魔方初始状态 ##三大变换 #对A(红色面)逆时针旋转90度;此时List应该是A面为俯视面的形式 U <- function(List) { unfold = Xup(List[[1]],List[[2]],List[[3]], List[[4]],List[[5]],List[[6]]) A = matrix(rep(0,48),6) for(i in 2:5)for(j in 4:7) A[9-j,2+i] = unfold[i,j] #坐标旋转由复数推导 unfold[2:5,4:7] = A[2:5,4:7] A = unfold[3:4,5:6] a = unfold[3:4,1:2] B = unfold[1:2,5:6] b = unfold[5:6,5:6] C = unfold[3:4,3:4] c = unfold[3:4,7:8] List = list(A,a,B,b,C,c,unfold) List } #U的逆变换,此时List应该是A面为俯视面的形式 V <- function(List) { unfold = Xup(List[[1]],List[[2]],List[[3]], List[[4]],List[[5]],List[[6]]) A = matrix(rep(0,48),6) for(i in 2:5)for(j in 4:7) A[j-2,9-i] = unfold[i,j] #坐标旋转由复数推导 unfold[2:5,4:7] = A[2:5,4:7] A = unfold[3:4,5:6] a = unfold[3:4,1:2] B = unfold[1:2,5:6] b = unfold[5:6,5:6] C = unfold[3:4,3:4] c = unfold[3:4,7:8] List = list(A,a,B,b,C,c,unfold) List } #对B(橙色面)逆时针旋转90度;此时List应该是B面为俯视面的形式 F <- function(List) { unfold = Xup(List[[3]],List[[4]],List[[2]], List[[1]],List[[5]],List[[6]]) A = matrix(rep(0,48),6) for(i in 2:5)for(j in 4:7)A[9-j,2+i] = unfold[i,j] #坐标旋转由复数推导 unfold[2:5,4:7] = A[2:5,4:7] B = unfold[3:4,5:6] b = unfold[3:4,1:2] a = unfold[1:2,5:6] A = unfold[5:6,5:6] C = unfold[3:4,3:4] c = unfold[3:4,7:8] List = list(A,a,B,b,C,c,unfold) List } #F的逆变换,此时List应该是B面为俯视面的形式 E <- function(List) { unfold = Xup(List[[3]],List[[4]],List[[2]], List[[1]],List[[5]],List[[6]]) A = matrix(rep(0,48),6) for(i in 2:5)for(j in 4:7)A[j-2,9-i] = unfold[i,j] #坐标旋转由复数推导 unfold[2:5,4:7] = A[2:5,4:7] B = unfold[3:4,5:6] b = unfold[3:4,1:2] a = unfold[1:2,5:6] A = unfold[5:6,5:6] C = unfold[3:4,3:4] c = unfold[3:4,7:8] List = list(A,a,B,b,C,c,unfold) List } #对C(黄色面)逆时针旋转90度;此时List应该是C面为俯视面的形式 R <- function(List) { unfold = Xup(List[[5]],List[[6]],List[[3]], List[[4]],List[[2]],List[[1]]) A = matrix(rep(0,48),6) for(i in 2:5)for(j in 4:7)A[9-j,2+i] = unfold[i,j] #坐标旋转由复数推导 unfold[2:5,4:7] = A[2:5,4:7] C = unfold[3:4,5:6] c = unfold[3:4,1:2] B = unfold[1:2,5:6] b = unfold[5:6,5:6] A = unfold[3:4,7:8] a = unfold[3:4,3:4] List = list(A,a,B,b,C,c,unfold) List } #R的逆变换,此时List应该是C面为俯视面的形式 K <- function(List) { unfold = Xup(List[[5]],List[[6]],List[[3]], List[[4]],List[[2]],List[[1]]) A = matrix(rep(0,48),6) for(i in 2:5)for(j in 4:7)A[j-2,9-i] = unfold[i,j] #坐标旋转由复数推导 unfold[2:5,4:7] = A[2:5,4:7] C = unfold[3:4,5:6] c = unfold[3:4,1:2] B = unfold[1:2,5:6] b = unfold[5:6,5:6] a = unfold[3:4,3:4] A = unfold[3:4,7:8] List = list(A,a,B,b,C,c,unfold) List } #魔方的变换 Transform <- function(Cha) #输入由U/V/F/E/R/K构成的字符串 { Cha = unlist(strsplit(Cha,split="")) #将字符串的字母逐个拆开 for(i in Cha) { if(i=="U"){cube = U(cube)} if(i=="V"){cube = V(cube)} if(i=="F"){cube = F(ABup(cube)); cube = BAup(cube)} if(i=="E"){cube = E(ABup(cube)); cube = BAup(cube)} if(i=="R"){cube = R(ACup(cube)); cube = CAup(cube)} if(i=="K"){cube = K(ACup(cube)); cube = CAup(cube)} draw(cube[[7]]) Sys.sleep(0.2) } cube[[7]] } Transform(rep("RVE",30))
代码说明: