标题: NSFOCUS旧友记--yuange的魔方人生 创建: 2021-12-18 21:25 更新: 2021-12-26 12:25 链接: http://scz.617.cn:8/body/202112182125.txt 大学时跟一个同学学过魔方。2009年教女魔头和侄女玩，教的就是大学时的套路。 2021年教陈北雁玩，翻出大学时的笔记，发现其本质上是层先法，只不过比流行的层 先法套路更土，涉及的公式更少，恢复起来更慢。我智商平庸，记不住CFOP/PLL或其 他什么公式，没指望跟人拼手速，所以慢对我无所谓。 云海一看不是比快，而是比慢，按捺不住比慢的心，分享了一个更慢的套路。前两层 无所谓，还原第三层时利用"FR相交棱"做缓冲区，总共两个公式，一个用于换角，另 一个用于就地翻转，比传统层先法公式少很多。为啥慢？因为需要观察后做点计算。 这个套路比大学时学的好，适合智商平庸的我。 有天我在网上问，假设白U绿F，如何快速还原图0，有啥现成的公式？ (0.jpg) 该图不是层先法还原6面时出现的，完全是把玩魔方、观察变化时刻意制造的。当时 微博上有两名网友给了回答。 CrozeLee: 白U红F会好理解一点，U'L'，接着做个顺三棱换，再LU回去 这个办法不错，适用于会"顺三棱换"的人。CFOP/PLL中"顺三棱换"公式是 R2URUR'U'R'U'R'UR' 假设白U红F，从6面同色制造图0，可以U'L'，接着做个逆三棱换，再LU回去。CFOP/ PLL中"逆三棱换"公式是 RU'RURURU'R'U'R'2 大学时的土法虽然没有直接的顺三棱换，但由两个其他套路组合后亦可达到顺三棱换 的效果，所以他这个办法对我也适用。 另一个回答 失去的生活习惯: U2 R F B' D' R' D F' B R' U' 硬撸的，不知道公式 这个答案完全切题，假设白U绿F，我还真照着拧回去了，相当佩服这些能硬撸还原的。 另有一些微信朋友的回答似乎是错的，不提了。然后，"我有一个朋友"系列，yuange 出场了。 scz: 不是为了还原六面，单纯寻找各种最小变换。 yuange: 我大一接触自己研究就是你这个思路，寻找最小的变换，然后就可以简单的 解决了 他是山东大学数学系的，不是山寨数学系的，这中间区别很大。我跟yuange认识有二 十多年，知道他在数学、网络安全、逆向工程方面很强，但不知道他还有魔方这一面。 yuange年轻时在攻击面上展现过"指哪打哪"的才华，有过很多相当传奇的经历，故事 性极强。我俩曾经在西坝河那边同住过两年，半夜从公司回住处的路上会聊七聊八。 但他还在世，我不方便传播"小道消息"。 有天我和bluerust聊起yuange scz: 他那时搞XXX确实很有一套，手里XXX早期0day很多，真地是指哪打哪，搞XX、 XX、XXXX的经历，确实无人可比。那些事故事性、传奇性很强，被他浪费了。 bluerust: 去开个blog，漏洞往事，把东西整理出来，我能做编辑帮处理排版和表述 scz: 他缺你这么个秘书 bluerust: 对，就别(略)，把那些故事写出来，整成一个系列，这多cool，能成经典， 穿插故事性陈述，老少咸宜 scz: 他要能写，能整一堆XX回来，这个适合他，真事。我是现在没时间，不然我可 以友情帮他整理 bluerust: 可以以访谈录的形式搞，靠袁哥自己说，只能是乱七八糟的。得有人不断 引导他，把细节全挖掘出来。 scz: 我擅长啊，等我老了来干这事 bluerust: 得捉紧，哥你等得起，别到时袁哥都痴呆了，你问他，今天天气好不好， 他答，我那时(略) scz: 这也是有可能的哈。。。 tt、yuange、scz、ipxodi这几个本科是一级的，谁先痴呆、谁先进火葬场还真不好 说。我未见等得起，万一哪天我先痴呆了呢？所以有时想起啥记点啥。2021.10.23讲 过一个关于yuange的SMB漏洞小八卦，这个是公开过的，只能当成八卦听，不够传奇。 下面是yuange在微信上回复我前述提问时写的，这个文字风格很yuange，正如二十年 前他那些Exploit源码一样，一言难尽。 yuange: 我不记那些公式，全靠正交三棱这个基本的交换，可以全部自己玩出来。基本的公式， 左手拿着一个面朝着自己，另一个手转动，就转最右边和最上面的，一次转动转90度， 一个基本的转动上右下左，这样就只有正交三条棱在交换。一次是左上角和右下角顶 点交换，对着自己那条棱两个顶点交换，三条棱的三中点轮换。这样6次是复原，顶 点是2次复原，中点是3次复原。上是最右一面向上转动90度，下是最右向下转90度， 左是最上面一层向左转90度，右是最上面一层向右转90度。 上右下左，就是最右一面向上转90度，最上面一层向右转90度，最右一层再向下转90 度，最上面一层再向左转90度。(scz: RU'R'U) 保持这个正交三棱做交换空间，先把别的一个个调整好，最后再调整这个正交三棱。 这样不用记忆公式，一步步就自己玩出来了。当然肯定没有记忆公式那么快。这是我 大学时候研究出来的自己独到的解法。 这个基本动作1-6次方或者-1到-6次方就可以简单的算出来。玩除了正交三棱之外的 时候可以把位置和颜色都先对好，不过最上面那一层的时候可能需要算一算顶点的交 换次数是不是偶数次了，因为这个基本动作的结果是顶点2个交換，所以最上面那一 个面的时候如果顶点还需要奇数个交換，那就需要最上面一个面做一下旋转(4个顶点 轮换，等于三次交换)，这样就奇偶平衡了。最后三条正交棱位置调好后可以调整颜 色。 这其实可以看出里面的群论(交换群)的知识应用。 大学时自己独立玩出来的独特的解法。这个其实是真正的解出了魔方，因为找到了最 小交换空间。根据这个，也能很容易算出魔方数了。也很好解我以前出的题，一个魔 方摔散了，捡起来随机组装好，能玩出来的概率是多少？ 这个算法可以用程序轻易解出来任意状态魔方，就和解多元一次方程组一样，太简单 了。 (1.jpg) (2.jpg) 魔方数，就是魔方的状态数。三阶魔方中间是固定的，有8个角块可以互换，每个角 块可以旋转3个方向的面，有12个棱块可以互换，每个棱块有2个面可以旋转。 所以摔散了的魔方随机组装出来的状态数是8!*3^8*12!*2^12。 由前面的最基本的旋转位置和面或者群论知识可以得到，每次转动的交换都是偶数次， 所以最终交换必须是偶数次，也就是棱块和角块单独一样两个对换是做不到的。颜色 交换那个，可以得到单独一个角块的旋转是做不到的，单独一个棱块的旋转是做不到 的，所以魔方的状态数是自由组装数的1/(2*3*2)，也就是1/12。 就是摔散了随机组装起来，只有1/12的概率能玩出来。 三阶魔方的魔方数就是1/12*8!*3^8*12!*2^12=4.325*10^19，非常巨大的一个数字。 由此我们编程玩三阶魔方的时候随机打乱，就可以完全随机的排列12个棱块和8个角 块以及面方向。然后简单算一下兑换次数，如果偶数次就不用调整位置，奇数次就找 两个棱块或者角块交换一下就可以了。再就是算一下角块和棱块的面旋转数，调整一 下分别保证3倍和2倍就行了。这个是真的随机打乱的了。这个也可以看出来魔方虽然 状态数巨大，但其实状态之间约束不强，互相约束大致上就差不多是多元一次方程组 的水平，这个一次方程组不管你多少元，都是比较简单的，所以不要被魔方数的巨大 数字迷惑了。 这样其实魔方找到一个解比较容易，魔方的最终化简还没有看到谁研究。这个研究出 来了就解决了三阶魔方最短路径最多20步的证明了。 scz: CS专业必修课有《离散数学》，但我们学校教得不深，群论只讲了一点点，置换群完 全没有讲。看yuange这么说，我重新翻开《离散数学》。 (3.jpg) (4.jpg) 下面是《离散数学》中关于"置换"的一些知识，对数学不感兴趣的可直接略过。 -------------------------------------------------------------------------- 设有限集合A={a1,a2,...,an}，p是集合A到它自身的一个双射 / a1 a2 ... an \ p=| | \ p(a1) p(a2) ... p(an) / 序列p(a1)、p(a2)、...p(an)恰好是A中元素的重排，此时称p是A上的一个置换。若 集合A有n个元素，那么存在n!种A的置换，就是n个元素全排列的个数。A上任意两个 置换的积仍然是A上的一个置换。 / a1 a2 ... an \ I=| | \ a1 a2 ... an / I称为A上的恒等置换。 设b1、b2、...br是集合A中r个不同的元素，对于置换p有 p(b1)=b2 p(b2)=b3 ... p(br-1)=br p(br)=b1 对于属于集合A但不在b1...br中的其他x，有 p(x)=x 此时称p是长度为r的循环置换，简称长度为r的"循环"，可以另记为 p=(b1,b2,...br) 举个例子，设A={1,2,3,4,5}，循环(1,3,5)的另一种写法是 / 1 2 3 4 5 \ p=| | \ 3 2 5 4 1 / 若p为长度为r的循环，有 p=(b1,b2,...br)=(b2,b3,...br,b1)=(br,b1,b2,...br-1) 循环(b1,b2,...br)脱离集合A时没有意义，因为不知道bi之外的ai。 恒等置换I是长度为1的循环。两个循环的积不一定是循环。对于集合A上两个循环， 若A中任一元素都不同时出现在这两个循环中，则称这两个循环"不相交"。 设p1、p2是A上两个不相交循环，有p1。p2=p2。p1，不相交循环之间满足交换律。相 交循环之间不满足交换律。 集合A上非"恒等或循环"的置换可以写成长度不小于2的"不相交循环"的积。举个例子 / 1 2 3 4 5 6 7 8 \ p=| |=(7,8)。(2,4,5)。(1,3,6) \ 3 4 6 5 2 1 8 7 / 由于不相交循环之间满足交换律，所以上式有多种写法，随便交换循环的位置。 长度为2的循环又称为"对换"，设对换p=(ai,aj)，根据定义有p(ai)=aj、p(aj)=ai。 设p为长度为2的循环，即p是一个对换，有p。p=I，即对换的2次方等于I。 我猜，设p为长度为r的循环，有p的r次方等于I，即p^r=I，我没去证明，只简单验证 了一些数据，别当真。 每个"循环"可以写成多个"对换"的积，即 (b1,b2,...br)=(b1,br)。(b1,br-1)。...(b1,b3)。(b1,b2) 于是，每个置换可以写成多个"对换"的积，举个例子 p =(7,8)。(2,4,5)。(1,3,6) =(7,8)。(2,5)。(2,4)。(1,6)。(1,3) 若A上一个置换可以写成偶数个"对换"的积，则称其为"偶置换"。若A上一个置换可以 写成奇数个"对换"的积，则称其为"奇置换"。没有任何置换既是偶的又是奇的。 两个偶置换的积是偶置换，两个奇置换的积是偶置换，一个偶置换和一个奇置换的积 是一个奇置换。对于集合A，存在n!/2个偶置换，存在n!/2个奇置换。 若p是A的一个置换，对于任意正整数m，p^m也是A的一个置换。设p是A的一个置换， 必有一个最小正整数k，使得p^k=I，此时称k称为p的周期。k是不是也称为p的阶？ -------------------------------------------------------------------------- scz: 看完"置换"的相关数学知识，再来看yuange的"上右下左"，也就是(RU'R'U)。 (5.jpg) 暂不考虑各块颜色朝向，只考虑各块位置，(RU'R'U)相当于这个"置换" / 1 2 3 4 5 6 7 \ | |=(3,5)。(2,6,4)。(1,7)=(3,5)。(2,4)。(2,6)。(1,7) \ 7 6 5 2 3 4 1 / 从数学上讲，这是一个"偶置换"。直观效果是(3,5)互换、(1,7)互换、(2,6,4)逆时 针三轮换。 (2,6,4)=(2,4)。(2,6) 这应该就是yuange所说，三轮换相当于两个对换(的积)。 正交三棱上的(RU'R'U)是一个置换，这个置换的任意次方也是同一组正交三棱上的置 换，从数学上就表明，反复做(RU'R'U)不会影响正交三棱之外的其他块。yuange应该 是记得住(或者说算得出)1到6次方的所有置换。 scz: 我没有yuange那么聪明的脑子，后来用了一种相对简单的办法来应用他的思路。为了 陈述方便，定义一些操作的简写 A-(RU'R'U) // yuange的"上右下左" B-(L'ULU') // B是A的"镜像对称"操作 C-(U'RUR') // C是A的逆操作 D-(UL'U'L) // D是B的逆操作 Y-整体顺转90度 ABCD只影响正交三棱，分别对应不同的置换，完全不影响其他块。ABCD的操作写出来 不直观，实际拧一下就会发现，其实全部同源，根本不需要记BCD，只记A就能全记住。 三次A操作对于正交三棱相当于这个"置换" / 1 2 3 4 5 6 7 \ A^3=| |=(3,5)。(1,7) \ 7 2 5 4 3 6 1 / 直观效果是(3,5)互换、(1,7)互换，不影响其余所有块。这个可以拧魔方观察得到， 也可以做数学运算得到 (3,5)。(2,6,4)。(1,7)。(3,5)。(2,6,4)。(1,7)。(3,5)。(2,6,4)。(1,7) = (3,5)。(2,6,4)。(2,6,4)。(2,6,4)。(1,7) = (3,5)。(1,7) ABCD的三次方都只影响正交三棱的四个角块，不影响其余所有块，相当于最小"换角" 公式。 两次A操作对于正交三棱相当于这个"置换" / 1 2 3 4 5 6 7 \ A^2=| |=(2,4,6) \ 1 4 3 6 5 2 7 / 直观效果是(2,4,6)顺时针三轮换，正交三棱四个角块都在原地，但翻转过。这个可 以拧魔方观察得到，也可以做数学运算得到 (3,5)。(2,6,4)。(1,7)。(3,5)。(2,6,4)。(1,7) = (2,6,4)。(2,6,4) = (2,4,6) 通过ABCD的不同组合，可对同一组正交三棱上的7个块进行互换、就地翻转等。前面 没有演示"就地翻转"，可以引入更复杂的置换表示式来展现"就地翻转"，此处略。 如果需要处理的块不是正好位于正交三棱，完全可以通过简单旋转将它们"凑"到一个 正交三棱上，应用完ABCD之后，再"逆"简单旋转回去即可。 scz: 对于正交三棱上的三个棱块 A^3=I A^2=A^(-1) A^2=C 即两次A操作对三棱块的影响等价于一次C操作。同理，对于正交三棱上的三个棱块 A^6=I A^5=A^(-1) A^5=C 三次A操作后，三棱块就还原了，应该就是说yuange所说，棱块的阶是3。同理，两次 A操作后，四角块就还原了(暂不考虑颜色朝向)，应该就是yuange所说，角块的阶是2。 求一下最小公倍数6，即六次A操作后，正交三棱上的四角块、三棱块同时还原，即 A^6=I scz: (6.jpg) 图6是说，(1,2,4,3,5)依次轮换之后的效果。分两步走，第一步是 (1,2)。(4,5) // U'+B^3+U 第二步是 (2,5)。(3,4) // B^3 scz: (7.jpg) 图7需要(1,3,4)依次轮换，就是yuange说的三个顶点三轮换。先做个数学变换 (1,3,4)=(1,4)。(1,3)=(1,4)。(2,5)。(2,5)。(1,3) 分两步走，第一步是 (1,4)。(2,5) // U'+A^3+U 第二步是 (2,5)。(1,3) // U+B^3+U' scz: (8.jpg) 图8是个小作业，只剩两个角块就地翻转即可还原。云海的两个公式之一就是用于角 块的就地翻转，很容易还原图8。但本题要求，用ABCD这种思路还原，有兴趣的可以 试试。 scz: 自从学了yuange的这个思路，我也不用层先法玩魔方了。现在这样玩 a. 全花状态，先对6面十字棱，这步无需任何公式，想怎么拧就怎么拧。其实这步也 可以用ABCD完成。 b. 由于ABCD的3次方完全不影响所有棱块，针对前一步的结果可以放肆地用ABCD的3 次方两两换角，直至所有角块归位。 c. 再用ABCD的适当组合就地翻角，大多数时候都是四角同时翻转到位，少数时候可 能会出现图8或类似情况，就得重新规划ABCD组合。 (9.jpg) (10.jpg) (11.jpg) 这种玩法由于参照系比较"花"，对于人类来说，通过肉眼观察、计算、规划完成ABCD 组合时需要一点空间想像力，有时可能还需要一点记忆力，所以快不起来，可能是我 见过的人类最慢玩法。但是，用程序解方程的话，这种玩法不慢，甚至算是较优解， 无效步骤不多。 对我来说，这种新玩法的"可玩性"最高。主要是有趣，不需要面对各种神秘公式， ABCD对我来说都是一回事，每次规划都是主动而高效的(单就步数而言)，就是解多元 一次方程。由于我没有与人拼手速的志向，现在这种情况再满意不过了。 我的最终玩法没有动用CD操作，只用到了AB操作。按yuange的说法，只用A就可以， 更慢而已。这点很好理解，BCD和A都是正交三棱上的置换，可能A的某次方分别等于 BCD。yuange自己玩的时候应该是更高效地组合了ABCD，我看他多次提到C操作，而且 他应该不像我先对6面十字棱，搞不好早早就规划了致使若干棱块、角块同步归位、 翻转的ABCD组合。我智商平庸，必须先对6面十字棱，让参照系不要太花。如果觉得 智商跟我差不多，建议还是用我这简版法子为妙，别太自虐。 找个时间约一下yuange，我带上我的小魔方，他带上他的小魔方，给我现场演示一下 魔方神功。二十一年前同居时，我们只聊过网络安全，没聊过魔方，太可惜了。 scz: 2050年，陈北雁带着scz去参加老年大学招生，碰上yuange也来报名。二人正叙旧间， 一个老师站在门口扯开了噪子，现在内卷得厉害，我们这个老年大学要对各位进行分 班考试。说完，他掏出一个魔方。 scz: 你袁伯伯肯定进重点班了，你爹应该能进普通班 cby: 只有这两种班？ scz: 还有一种老年弱智班 cby: 看来我妈只能进这种班了 scz: 不，她考不上，只好在家帮你带娃 算了，前面都是在胡扯。不出意外的话，二十年后我就老年痴呆了，如果现在我努努 力，还可以快点。真到了那一天，可能不再认识在坐的各位，只好提前说一句，相识 一场，不胜荣幸。 -------------------------------------------------------------------------- (一些网友回复) 密码有误: 很早以前就想写个rubik cube group theory for kids，上网一看好多人写过类似内 容了(虽然不一定是for kids的)，立马放弃[呲牙][呲牙] 讲个段子 二战后法国数学教育大改革，成效显著，消息传到社会主义国家，苏联政府派数学家 去法国参观学习。 苏联数学家问一个小朋友： 「小朋友，5+3 等于几？」 「不知道。」 「那 3+5 呢？」 「不知道。」 「呃……好吧……」 「叔叔，叔叔，我虽然不知道 5+3 和 3+5 等于几，但是我知道 5+3 肯定等于 3+5。」 「哦？」苏联数学家眼睛一亮，「为什么呢？」 「因为这是一个阿贝尔群。」 yuange: 大概大一的时候才第一次接触到三阶魔方，开学时同寝室同学带来的玩具。农村娃出 身确实有点low，其实那时候的农村娃差不多都一样，玩具都是些不花钱的自制玩具。 没多久自己独立玩出来的自己想要的找到最小交换空间的解法，有点类似解多元一次 方程组，这个就有点像行列式方法解多元一次方程组一样真正的解出来了魔方，不需 要记忆公式。 那时候没有网络，才接触到魔方如果能够这样去想(找最小的交换空间)自己独立解出 来，还是需要一点独立动手能力的。刚好高中自学了一些群的知识，所以有了数学基 础，这点非常重要。因此我推荐scz去看了置换群的相关资料再回过来玩，很多东西 也就很容易理解就简单得多了。 有了三阶魔方基础其它的基本类似。 模糊记得以前高中看的《群论》上面写的是研究生教材，我记得我们数学系大学好像 就没学群论。现在群论知识解魔方的教程还是比较多了，因为这个才是其本质。