快好知 kuaihz订阅观点

 

魔方的原理是什么?

(小石头,站在偏数学的角度,来回答这个问题。简单一句话,魔方的原理就是:魔方群在状态集上的作用,具体回答如下:)

魔方

整体来看,魔方(Rubik"s cube)是一个立方体,一共有六个面 (surface),我们分别用 U(up 上)、D(down 下)、F (front 前)、B(back 后)、L(left 左)、R(right 右)来标识,不妨规定:U 对应 黄(yellow)、D 对应 白(white)、F 对应 蓝(blue)、B 对应 绿(green)、L 对应 橙(orange)、R 对应 红(red)。

令,M = {U, D, F, B, L, R},当 任意面 f ∈ M 朝向我们时,对 f 面 顺时针 旋转 90°, 被定义为 魔方的 基本操作(base operation),同样用 f 面 的 面标识 来表示 这种基本操作。所以 M 也代表 魔方的全部基本操作

对于,任意 基本操作 g, h ∈ M,gh 称为 g 和 h 的 复合(compose), 表示 先 g 操作 再 h 操作 的复合操作。可以验证,复合满足结合律, 这样以来,以 M 为生成元 在复合操作下会生成一个群 G = (M),称为 魔方群(Rubik‘s cube group)。其中,G 的 幺元,记为 1, 表示 没有进行任何操作操作

什么是群?

群就是定义了一种运算 的集合 ,其 满足:

集合对运算封闭,即,对于任意 都有 ( 注意:和乘法运算类似,习惯省略不写 ) ;

运算有分配律,即, 对于任意 都有 ;

有幺元,即,存在 使得 对于 任意 都有 ;

有逆元,即,对于任意 都存在 的逆元 使得 。

什么是 M 生成的群?

数学上定义:包括 M 中元素的 最小的群,为M生成的群,记为 (M)。实际上,可以 对 M 中任意操作 g 和 h 不断的 进行 复合运算,如果得到的新复合操作 gh 不在 M 中,就 gh 添加到 M 里,直到 M 不再增加,这样就得到了 (M)。

同一基本操作 g, 连续四次 复合 就是 对 g 面 顺时针 旋转 360°,这相当于 没有操作,即,

gggg = 1

从而有:

gg³ = 1

也就是说 g³ 就是 g 的逆元 g⁻¹ ,相当于 对 g 面 逆时针 旋转 90°。

另外,由 gggg = 1 还可以得到:

g²g² = 1

这说明 连续两次 复合 g² 的逆元 就是自己,即,顺时针 旋转 180° 相当于 逆时针 旋转 180° 。

魔方状态

三阶魔方被细分为 3 × 3 × 3 = 27 个 立方小块(cubie)。其中,位于 中间核心的 那个 小块 不会受到 魔方操作 的影响到,而对于 每个 面中心的 那个 小块 魔方操作 同样无法改变它的位置,因此 魔方操作 所能 影响到的 小块 为 27 - (1 + 6) = 20 个。

这 20 个 受 魔方操作 作用的 小块,又分为 两类:

位于魔方 8 个角 处的 角(corner)块,它们有3个有效 小面(facet);

位于魔方 12 个棱 处的 棱(edge)块,它们有2个有效 小面;

由于,每个面的 中心块 保持位置不变,因此对于打乱的魔方,可以依照 中心块 来 确定 魔方的各个面 方向。魔方在初始(或 还原)状态下,角块 和 棱块 的每个 小面 和 该小面 所在面 的 中心小块 颜色保持一致。

我们用 角块(或 棱块) 的各小面 颜色所对应的 标识 的小写字母 的组合来标识 角块(或 棱块):

对于 角块,三个小面 x, y, z,有 6 种排列方式,这里 使用 从 u 或 d 开始 的 顺时针 排列方式,即,角块标识 xyz 保证 x = u/d 并且 x →y → z 是顺时针;

对于 棱块,二个小面 x, y, 有 2 种 排列方式,这里 使用 从 u 或 d(f 或 b) 开始 的 排列方式,即,棱块标识 xy 保证 x = u/d/f/b;

根据上面的规则,八个角块分别表示为:ufl, urf, ubr, ulb; dbl, dlf, dfr, drb; 十二个棱块分别表示为:ub, ur, uf, ul; bl, br, fr, fl; db, dr, df, dl

注意:六个中心块 分别表示为:u, d, f, b, l, r,核心块 一般用 o 表示 。

更进一步,对于角块 xyz,我们用 xyz 表示 x 小面,yzx 表示 y 小面,zxy 表示 z 小面,对于棱块 xy ,我们用 xy 表示 x 小面,用 yx 表示 y 小面,于是,我们就得到了 带有标注 的 8 × 3 + 12 × 2 = 48 个 小面。将,全体小面记为 T,则 任意 操作 g ∈ G 就变成了 T 上的 一种 置换(位置变换)。以 F 操作 为例,

观察发现, 小面 fur 经过 F 操作 置换 为 小面 flu,即,F(fur) = flu,另有 F(flu) = fdl、F(fdl) = frd、F(frd) = flu,于是 在 F 操作下,以上 4 个置换 形成了 一个 置换圈:

我们称其为 轮换(cycle),记为 (fur flu fdl frd) 。

参与轮换的 小面 可以是任意多个,值得注意的是:任何一个小面 a 的 轮换 (a) 相当于 不做 置换,有, 1 = () = (a) 。

当然,实际上 F 操作 包含 多个 轮换,将这些轮换 以复合的方式,聚合在一起,就是定义了一个 完整 F 操作

F = (fur flu fdl frd) (fu fl fd fr)(rfu ufl lfd dfr)(rf uf lf df)(rdf urf luf dlf)

同理,我们可以将 其它魔方操作 定义为 轮换 的复合。

注意:为了方便,我们也可以用 1- 48 的 正整数,来替代 上面 S 中 对小面 的编码。

T 上的所有 置换函数,在函数复合下,组成 置换群 S₄₈。但是,因为 角块的面永远置换不到棱块的面,所以 G 仅仅是 S₄₈ 的子群。

用离散的小面来记录魔方的状态过于粗犷,重新审视魔方,我们会得到如下结果:

每个立方块都是一个整体,在任何魔方操作下,组成它的小面不会分离;

每个立方块,有两种状态信息:位置 和 方向;

角块 和 棱块 在 魔法操作下 相互独立,即,角块 永远不可能 转到 棱块 上,反之亦然。

基于,以上分析,我们首先, 分别 对 角块 和 棱块 进行定位(location):

角块:ufl = 1, urf = 2, ubr = 3, ulb = 4; dbl = 5, dlf = 6, dfr = 7, drb = 8;

棱块:ub = 1, ur = 2, uf = 3, ul = 4; bl = 5, br = 6, fr = 7, fl = 8; db = 9, dr = 10, df = 11, dl = 12;

令 C = {1, 2, 3, 4, 5, 6, 7, 8}, 这里包含 所有 角块的位置信息,可以很容易将 基本操作 对 角块位置的 改变写成轮换形式:

U = (1 2 3 4),

D = (5 8 7 6),

F = (1 6 7 2),

B = (3 8 5 4),

L = (1 4 5 6),

R = (2 7 8 3)

显然,G 作用在 C 上 是 置换群 S₈ 的子群。

同理,令 E = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12},基本操作对于 棱块 位置的改变写成轮换形式为:

U = (1 4 3 2),

D = (9 10 11 12),

F = (3 8 11 7),

B = (1 6 9 5),

L = (4 5 12 8),

R = (2 7 10 6)

同样,G 作用在 E 上 是 置换群 S₁₂ 的子群。

然后,我们分别对 角块 和 棱块 进行定向(orientation):

角块:u/d 为定向面,xyz = 012;

棱块:u/d/f/b 为定向面,xy = 01;

对于保持 定向 信息,我们只需要定义,定位位置 当前 立方块 的 定向面 对应 的 编号就可以了。而对于 基本操作,对 定向的 改变,我们也只需要 记录,原始状态下,经过 基本操作后,各个 定位位置,的 定向面 对应 的 编号就可以了。如果,原始状态下,即, 定向面的编号为 0,经过某操作,到新位置后,定向面编号为 n,则 原来 定向面的编号为 m,经同样操作,到新位置后,定向面编号就是 (n + m) mod k,对于角块 k = 3,对于 棱块 k = 2。0- 不旋转,1-逆时针旋转,2-顺时针旋转。

令,V = (0, 0, 0, 0, 0, 0, 0, 0) 表示 角块的所有定向,则 基本操作为对角块定向的改变为:

U = (0, 0, 0, 0, 0, 0, 0, 0),

D = (0, 0, 0, 0, 0, 0, 0, 0),

F = (1, 2, 0, 0, 0, 2, 1, 0),

B = (0, 0, 1, 2, 1, 0, 0, 2),

L = (2, 0, 0, 1, 2, 1, 0, 0),

R = (0, 1, 2, 0, 0, 0, 2, 1)

对于每一位来说都是 Z₃ ,总共 8 个 Z₃ 就是 Z₃⁸ ,但是 考虑 在 到 7 个 角块固定的情况下,我们无法 单独 旋转 剩下的那个,因此 G 在 V 上的作用 实际上 是 Z₃⁷。

令,W = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) 表示 棱块的所有定向,则 基本操作为对棱块定向的改变为:

U = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),

D = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),

F = (0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0),

B = (1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0),

L = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),

R = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

同理, G 在 W 上的作用 是 Z₂¹¹。

当以上编号混合在一起使用时,为了区分,分别用 c、e、v、w 作为 角块定位、棱块定位、角块定向、棱块定向 编号的前缀,并将编号写成下标。例如:

F = (c₁ c₆ c₇ c₂) (e₃ e₈ e₁₁ e₇) (v₁, v₂, v₀, v₀, v₀, v₂, v₁, v₀) (w₀, w₀, w₁, w₀, w₀, w₀, w₁, w₁, w₀, w₀, w₁, w₀)

辅助工具

在进行下一步分析之前,我们先编写一点 JavaScript 代码,以帮助我们,对 G 中的 操作进行复合。

魔方状态(state)的 格式为:

state:[[角块定位], [棱块定位], [角块定向], 棱块定向]

声明 魔方初始状态 s₀ 如下:

魔方操作(operation)的 格式为:

[[[角块轮换], ...], [[棱块轮换], ...], [角块旋转], [棱块旋转]]

基本操作声明如下:

声明,在给定状态上执行魔方操作的函数:

声明,从给定状态中分析出魔方操作的函数:

定义 复合 函数:

为了输出简洁,当所有角块(或,棱块)不发生旋转 时,用一对空括号表示。

最后,我们对基本操作进行必要的扩展:

换位子 和 共轭

对于 任意两个 魔方操作 g,h ∈ G,如果,g 和 h 的复合 满足交换律,则:

gh = hg

等式两边右乘 g⁻¹h⁻¹,有:

ghg⁻¹h⁻¹ = hgg⁻¹h⁻¹ = h1h⁻¹ = hh⁻¹ = 1

如果 不满足交换律,则:

ghg⁻¹h⁻¹ ≠ 1

令,[g, h] = ghg⁻¹h⁻¹,称其为 换位子(commutator)。

一般来说,魔方相对面 ,如: F 和 B,U 和 D,L 和 R 之间是可以交换的,即,

[F, B] = [U, D] = [L, R] = 1

所有,换位子 之间是可以交换的,即:

[[g₁, h₁] [g₂, h₂]] = 1

关于,换位子有 性质1:如果 g 和 h 两种操作,只 共同影响 一个 小块 k,其中 g 为 n → k,h 为 m → k,则有 [g, h] = (k, n, m),[h, g] = (k, m, n)。

例如,若 g = (c₁ c₂ c₃), h = (c₁, c₄ c₅),则 k = c₁, n = c₂, m = c₄,于是有:

即,[g, h] = (c₁ c₂ c₄),[h, g] = (c₁ c₄ c₂)。

性质1推论:如果 g 和 h 两种操作,共同影响 的小块,刚好 在 g 和 h 中 分别 形成 轮换 σ 和 τ,则有 [g, h] = [σ, τ]。

例如:若 g = (c₁ c₂ c₃ c₄)(c₅ c₆), h = (c₁ c₂ c₄ c₃)(c₇ c₈),则 它们的共同影响小块 c₁、c₂、c₃、c₄,分别 在 g 和 h 中,组成轮转 (c₁ c₂ c₃ c₄) 和 (c₁ c₂ c₄ c₃),于是有:

即,[g, h] = [(c₁ c₂ c₃ c₄), (c₁ c₂ c₄ c₃)]。

魔方群中还有另外一种 称为 共轭(conjugate)的复合方式:对于 任何操作 g,h ∈ G,称 ghg⁻¹ 为 h 关于 g 的共轭。

共轭具有 性质2:如果 h = (a b c) 而 g 将 A, B, C 分别映射到 a, b, c,则有 ghg⁻¹ = (A B C)。

例如:若 h = (c₁ c₂ c₃), g = (c₁ c₄)(c₂ c₅)(c₃ c₆),则有:

即,ghg⁻¹ = (c₄ c₅ c₆)。

魔方公式

好了!现在利用上面的知识,就可以开始构造魔方公式了。

寻找角块的换位公式

我们发现 B⁻¹ 关于 R⁻¹ 的 共轭 R⁻¹B⁻¹(R⁻¹)⁻¹ = R⁻¹B⁻¹R:

和 F²:

仅有 c₇ 共同影响,于是它们满足 性质1,有:

即,[R⁻¹B⁻¹R, F²] = R⁻¹B⁻¹R F² (R⁻¹B⁻¹R)⁻¹ (F²)⁻¹ = R⁻¹B⁻¹R F² R⁻¹B⁻¹R F² = (c1, c7, c8)。

注意:因为 (ab)(b⁻¹a⁻¹) = abb⁻¹a⁻¹ = a1a⁻¹ = aa⁻¹ = 1,所以 (ab)⁻¹ = b⁻¹a⁻¹。

这里 c₁, c₇, c₈ 不共面,考虑 R² :

刚好 将 1 ↦ 1, 2 ↦ 8, 3 ↦ 7,于是根据 性质2,有:

开头的 RR RRR = R ,于是最终得到 公式C:

即,

R²[R⁻¹B⁻¹R, F²]R⁻² = RB⁻¹RF²R⁻¹BRF²R² = (c₁ c₂ c₃)

寻找棱块的换位公式

我们定义一种新的操作 M:面对 F 面,顺指针旋转 F 和 B 面之间那个中间的面M。M 操作 只改变棱块:

我们发现 M(或 M)与 U²:

共同影响 e₄,因此 根据性质1,[M⁻¹, U²] 构成三轮换:

即,[M⁻¹, U²] = M⁻¹U²MU² = (e₂ e₄ e₁₀)。

其实,M⁻¹ 就相当于 FB⁻¹ 的复合,只不过,在执行 M⁻¹ 后,还做了 R 面朝向了 U 的动作。

这时 执行 U² 相当于 执行 R²,于是翻译为 基本操作 [M⁻¹, U²] = FB⁻¹R²BF⁻¹U²,验证:

最后, 根据 性质2,利用 R²U 将 这个 三轮换,换到同一个面上:

倒数第2, 3 项合并后,就得到了 公式D:

R²U[M⁻¹, U²]U⁻¹R² = R²UFB⁻¹R²BF⁻¹UR² = (e₁ e₃ e₂)

寻找角块的旋转公式

观察 D² 关于 RF⁻¹ 的共轭 RF⁻¹D²FR⁻¹:

与 U²:

它们,有共同的轮转 (c₁ c₃),于是根据 性质1推论,有:

[U², RF⁻¹D²FR⁻¹] = [(c₁ c₃), (c₁ c₃)] = (c₁ c₃)(c₁ c₃)(c₃, c₁)(c₃, c₁) = (c₁ c₃)1(c₃, c₁) = (c₁ c₃)(c₃, c₁) = 1

这样以来,[U², RF⁻¹D²FR⁻¹] 就没有了位置变换,仅仅剩下的就是旋转:

于是,我们就得到 公式 E:

[U², RF⁻¹D²FR⁻¹] = U²RF⁻¹D²FR⁻¹U²RF⁻¹D²FR⁻¹ = (v₁, v₀, v₂, v₀, v₀, v₀, v₀, v₀);

公式 E 分别 对 c₁ 和 c₃ 进行 逆时针 和 顺时针 旋转。

寻找棱块的旋转公式

M 和 U 分别执行4次会恢复,那么 MU 执行四次,即,(MU)⁴ 是什么呢?

我们神奇的发现:

(MU)⁴ = F⁻¹BLF⁻¹BDF⁻¹BRF⁻¹BU = (w₁, w₁, w₀, w₀, w₀, w₀, w₀, w₀, w₀, w₁, w₀, w₁)

即,(MU)⁴ 只对 e₁, e₂, e₁0, e₁₂ 旋转;

同样,(MU⁻¹)⁴ :

(MU⁻¹)⁴ = F⁻¹BL⁻¹F⁻¹BD⁻¹F⁻¹BR⁻¹F⁻¹BU⁻¹ = (w₀, w₁, w₁, w₀, w₀, w₀, w₀, w₀, w₁, w₀, w₁)

即,(MU⁻¹)⁴ 只对 e₂, e3, e₁0, e₁₂ 旋转;

因为 棱块旋转 2 次就等于没有旋转,于是 (MU)⁴ 和 (MU⁻¹)⁴ 的复合 结果 只对 e₁ 和 e₃ 进行旋转,这就是 公式F:

(MU)⁴(MU⁻¹)⁴ = (w₁,w₀, w₁, w₀, w₀, w₀, w₀, w₀, w₀, w₀, w₀)

可以验证:

暴力搜索

两轮换 称为 对换,在魔方群中 单独的 对换操作,是不可能的 因此 三轮换,成立 公式构造的 关键,除了上面利用 性质1 来 找寻 三轮换 的 方法为,我们还可以用计算机,进行暴力搜索。例如:在 2 个 R,3 个 R⁻¹, 3 个 U, 2 个 U⁻¹ 的全排列中,进行三轮换搜索:

我们得到:

即,R⁻¹U⁻¹RURURU⁻¹R⁻¹U⁻¹ = (e₃ e₄ e₁₀)。然后 根据 性质2,利用 R² 将 这个 三轮换,换到同一个面上:

同样,将开头的 5 个 R 合并,就得到 和 公式D 类似的公式:

RU⁻¹RURURU⁻¹R⁻¹U⁻¹R² = (e₂ e₃ e₄)

对于旋转来说,以上的分析,最少只能的道 两个 角块(或 棱块)的旋转,我们无法做到 仅仅旋转 一个角块(或 棱块)。

上面,给定的公式都保证 角块(或 棱块)的旋转 时,所有小块位置不变,但 实际上,不一定需要这么严格,我们可以允许 与旋转小块同处一个面 内 小块的位置变换。通过暴力搜索,我们得到了公式B:

即,

RUR⁻¹URU²R⁻¹ = (c₁ c₃)(c₂ c₄)(e₁ e₂ e₄)(v₂, v₂, v₀, v₂, v₀, v₀, v₀, v₀);

以及,公式A:

即,

FRUR⁻¹U⁻¹F⁻¹ = (c₁ c₂)(c₃ c₄)(e₁ e₂ e₃)(v₀, v₂, v₁, v₀, v₀, v₀, v₀, v₀)(w₀, w₁, w₁, w₀, w₀, w₀, w₀, w₀, w₀, w₀, w₀, w₀);

公式 AB 都是 只 改变 顶层 位置的 操作

其实,公式A就是 F[R, U]F⁻¹,其中 [R, U]:

[R, U] 的功效是 (e₁ e₂ e₇) ,即,将 顶层棱块 e₁ e₂ 和 中层 棱块 e₇ 轮换,但副作用 (c₂ c₇) 变动了 底层。不过幸运的是,我们找到了 [F⁻¹, U⁻¹]:

[ F⁻¹, U⁻¹] 的功效 和 [R, U] 类似,而其副作也是 (c₂ c₇)。因为 (c₂ c₇)(c₂ c₇) = 1,所以 [U⁻¹, F⁻¹] 的 刚好可以抵消 [R, U] 的副作用。于是,我们就得到了 公式A的附带公式:

[R, U] [ F⁻¹, U⁻¹] 和 [ F⁻¹, U⁻¹] [R, U]

功效分别是 (e₁ e₂ e₇ e₄ e₃) 和 (e₁ e₂ e₃ e₄ e₇),即,将顶层的 四个棱块 与 中层 的 棱块 e₇ 轮转。

魔方数学原理的指导下,通过这种计算机暴力搜索的方式,我们还可以找到很多有用的公式,目前紧紧OLL公式就有 57 个,而更多的复杂公式几百上千。

众所周知的 ”七步公式还原法“(层先法) 就包括了从这些公式中选出来的 一组基础公式(包括上面提到的 公式ABCD)。(七步公式还原法,已经有条友在回答中详细介绍过了,我这里就不累述了。)

不知不觉,已经写了 5千余字了。关于魔法群还有很多更深入的内容,例如:上帝数 等,由于篇幅有限,这里不能一一展开,以后有机会再说。

(小石头,数学水平有限,出错在所难免,希望各位老师和同学批评指正。)

(补充 2019/10/30)

我将辅助工具的代码放在这里,以便想要自己试验的条友复制粘贴。

运行环境:chrome 浏览器;

文件名:rc.html,包含代码:

文件名:rc2.html,包含代码:

本站资源来自互联网,仅供学习,如有侵权,请通知删除,敬请谅解!
搜索建议:魔方的原理是什么?  魔方  魔方词条  原理  原理词条  什么  什么词条  
综合

 学语文最重要的是什么?

语文学科,是所有学科中最基础的学科。因为它不光是提升孩子的语言运用的能力,还担负着思维能力,审美能力的培养和文化传承的使命。学语文,最重要的是做好三件事:语言文...(展开)