魔方吧·中文魔方俱乐部

标题: [FM]状态集转换法——Ryan的两封信 [打印本页]

作者: noski 时间: 2008-3-24 14:55:00 标题: [FM]状态集转换法——Ryan的两封信

这是Ryan Heise关于Thistlethwaite方法的两封E-mail
Translated by noski.

注：FMC，Fewest Moves Challenge。
For 3x3x3 Rubik's Cube.

在2002年的圣诞节，我研究了Thistlethwaite计算机算法的人脑计算理论。
下面是我在Yahoo! speedsolvingrubikscube上发的有关这个方法的邮件。

Post 1:
From: Ryan Heise <[email=rheise@it]rheise@it[/email]....>
Date: Sun, 22 Jun 2003 11:30:52 +1000
To: Ron van Bruchem <[email=rvb@chello]rvb@chello[/email]....>
Subject: Thistlethwaite, human version

On Sat, Jun 21, 2003 at 06:13:28PM +0200, Ron van Bruchem wrote:
> Hi Ryan,
>我对你的主意很感兴趣，请给我讲讲你提出的这套方法，以及每一步所使用的公式。

第一阶段：<U,D,L,R,F2,B2> 状态集（group）
　　- 简单，没有公式。
第二阶段：<U,D,L2,R2,F2,B2> 状态集
　　- 把上/下层的棱块移到上/下层（简单，没有公式）
　　- 把角块移到上/下层（8-60个公式）
第三阶段：<U2,D2,L2,R2,F2,B2> 状态集
　　- 角块（1-2个公式）
　　- 棱块（1-4个公式）
第四阶段：各块归位
　　- 角块（凭直觉）
　　- 棱块（凭直觉）

各个步骤的细节

**第一阶段**

　　完成这一阶段平均需要4.6步。

**第二阶段** 棱块

　　这一步骤很简单，如果你愿意，你可以研究一下所有的20-30种情况。我忘记了确切的数字。完成这一步骤平均需要4步。

**第二阶段** 角块

　　我用的方法和Gaetan相同，首先把三个角移到同一边，然后做8个公式中的一个。当然你可以直接学会所有的60种情况（我记不清确切数字了）。我认为这一步平均需要8.5步。

**第三阶段** 角块

　　在第三阶段，很重要一点是要先做角块，因为因为你很难看出是否它们在U2D2L2R2F2B2状态集（group）中。仅仅让每个面上只包含其自身颜色和相对面颜色是不够的。当不需要考虑棱块时，完成这一步骤需要的公式会更短。

　　在这里，我只是描述了只要两个公式的最简单的技巧，但这个技巧需要你有很快的手指和大脑：

　　首先，分离上/下颜色（每个颜色都在各自的面上），平均需要3.2步。例如应该是这样：所有的红色角都在顶层，所有的橙色角都在底层。

　　现在，几对相邻的角块可能匹配，也可能不匹配。我们的目标是让它们或者全匹配，或者全不匹配。所以，在这一步，我们把与众不同者找出来（无论匹配或不匹配），然后解决它们，让它们与其它对一样。这里一共有4对角块，所以与众不同者，只可能是一对两对。

　　一对的情况：转动你的魔方，把这一对置于UF的位置，并做R'FR'B2RF'R。这是对角块移动的一个修正，不用考虑每个角块的具体位置。

　　两对的情况：转动你的魔方，把这两对置于F面上（你可能需要把某一个移动过去），并做R2UF2U2R2U。（如果你需要事先把某一对移过去的话，可以使用一点小技巧来优化。。）

　　我花了很长时间来寻找其它的用更短步数来完成这一步骤的方法，并且也找到了一些，但这个方法到目前为止绝对是最快的一个。

**第三阶段** 棱块

　　4种情况-很简单（2、4、6或8个错棱（bad edges）），平均步数6.1步。

　　到目前的步数一共为33.4，显然，为了达到最终平均少于40步的目标，寻找更短的步数是必要的。我也找了一些捷径，但我认为它们不值一做，因为我可以更快的执行这个稍长一点的方法。

**第四阶段** 终章

　　我想，你对此已经想好策略了。角块，然后棱块。我觉把角块的所有情况都学会是可能的（大概150个，但很好记）。

　　一个缺点是那些180度旋转（Double turns）比较难做，但我尝试了几个公式，感觉它们可以做得足够快。我想这个方法最大的益处就是反应时间快速和不用去思考。另一个好处是当你还原了魔方的时候，你会觉得好Cool！不到最最后，没有一个块是还原好的。。

　　以上，我列出了没有优化的每一步骤。合并步骤，或者适机采用不同的顺序都是可以的。上面的基本的方法，如果你学会了每一步的所有情况，就能够给出一个平均步数为45.7步的答案。

Ryan

http://www.ryanheise.com/cube/human_thistlethwaite_algorithm.html

[ 本帖最后由 noski 于 2008-11-25 00:38 编辑 ]

作者: noski 时间: 2008-3-24 14:55:26

Post 2:
To: speedsolvingrubikscube@yahoogroups.com
From: Ryan Heise <[email=rheise@progsoc]rheise@progsoc[/email]....>
Date: Wed, 9 Jul 2003 15:42:19 +1000
Subject: [Speed cubing group] Method with the fewest non-obvious algorithms - zero

On Tue, Jul 08, 2003 at 05:09:13PM -0000, tomrokicki wrote:
> So what method requires the fewest algorithms that aren't "obvious"
> or logically clear?

使用简化的Thistlethwaite方法，可以不用任何难懂的公式就能还原魔方。

步骤1 不需要公式
步骤2 用一个5步的公式
步骤3 用一个7步的公式和一个4步的公式
步骤4 用两个6步的公式

因为所有的公式都很短很简单，所以使用这一方法人可以说，他们还原了魔方，并且懂得他们是如何做到的！
也许你觉得这还不够简单，但这是一个还原魔方的有趣的方法，如果你能做到的话。

**步骤1**

　　把魔方转到<L2,R2,F,B,U,D>状态集（我称它为G1）。也就是说，把魔方转到一个状态，使得它可以只使用L2,R2,F,B,U,D来还原。在这个方法中，在步骤4之前，把相对面的颜色看成相同的，会对你有帮助。我们把左/右面的颜色称为“绿色”（这在步骤1中并不重要），上/下面称为“红色”，前/后面称为“白色”。

　　一旦进入G1状态集，就不可能再翻转棱了，所以为了让魔方进入G1状态集，我们所要做的就是确保所有的棱块都正确翻转。首先，你需要找出未正确翻转的棱块（Bad edges）。一个未正确翻转的棱块是指，如果只使用G1中允许的转动（L2,R2,F,B,U,D）去把这个棱块归回原位，它的朝向是错误的。（当然了，只为判断，你用不着把它转回原位去）

　　未正确翻转的棱总是偶数个，在0到12之间，或者平均6个。翻转棱的唯一方法就是把L层或R层转动90度，这样会一下子把这一边的4个棱全部翻转。为了翻转4个棱，你只需要简单把它们都放在一边（比如左边），然后把该层转动90度。为了翻转2个棱，你可以把其中一个放到L层上，再转90度，这样2个就变成了4个（新出现的3个+原来的1个），就又可是用刚才的方法了。

　　在步骤1的末尾，你应该看到，没有一个红色的棱朝向前或后，没有一个白色的棱朝向上或下。在别人看来，你的转动简直没有任何成果！然而现在，12个棱都已处在一个比较好的位置上了。

**步骤2**

　　把魔方转到<L2,R2,F2,B2,U,D>状态集（我称它为G2）。在这个状态集中，中层的棱块都位于中层（被UD夹在中间的层）上且被正确翻转了，而顶部和底部的棱块只能在这两层之间交换且不会再被翻转。在步骤2的末尾，你应该看到，顶面和底面只有红色，而在中层，绿色朝向左/右，白色朝向前/后。

　　切记我们刚刚进入G1状态集，所以为了进入G2状态集，我们只能使用G1中允许的转动（L2,R2,F,B,U,D）。我们希望在顶层和底层各得到一个红色的Cross，而在12个棱块中，有8个是红色，由于空间有限，必有至少4个已成为Cross的一部分。通用的策略是，先在顶层和底层各放3个红色的棱，然后调整一下U和D，使得Cross的缺口都朝前。这时，两个缺失的红色棱块一定在中层的某处（如果不是，那一定有4个红色棱同时在顶层或底层，而不是3个）。用180度旋转（L2,R2,F2,B2）把这剩下的两个红色棱移到中层朝前的地方，再把F层转动90度。当这样把棱块做好时，我们得到了“对称”的结构，所以现在我们可以把整个魔方绕着U-D轴转动，随时改变一下前和后的观念了。很方便。

　　现在开始解决角块，我们可以一次翻转两个角块。把一个角块放在LUF位置上（角A），把另一个角放在FDR位置上（角B），然后做：

　　R'D - 翻转角B
　　L2 - 交换角B和角A
　　D'R - 在返回时翻转角A

　　重复的这样做直到所有的角块都被正确翻转。你应该让所有的红色都在顶面或底面上。

**步骤3**

　　把魔方转到<L2,R2,F2,B2,U2,D2>状态集（我称它为G3）。在前面的状态集中，你只是把顶面和底面都变成了相对面的颜色（红色），在这一步骤，你要把前/后面（白色）、左/右面（绿色）也做到这样子。在G3状态集中，每个角块只能处在四个位置中的一个，我称它为一个“环”。在魔方上只有两个环，8个角块分属其中。在G3状态集中，你能做的只能是180度转动，即交换一个环中的两个角块，同时交换另一个环中的两个角块。这就限制了角块可能的排列，也意味着简单的使每个面只有它本身的颜色和相对面的颜色是不足以满足G3的。

　　既然角块会出一点小问题，所以我们先使角块进入G3状态集，然后再处理棱块。现在为了判断是否满足G3，你必须要区分相对面的颜色了。在这里我用的颜色是红对橙、白对黄、绿对蓝。一个判断是否满足G3的简单方法是把所有红色的角块移到顶层，橙色的角块放在底层，这样这些角块分成四对，每一对可能是匹配的，也可能是不匹配的。当它们全匹配或全不匹配时，角块就进入G3状态集了。所有角块都匹配只有一种情况，所有角块都不匹配也只有一种情况（在两个层都有一对对角相交换）。做R2U2R2，就可以在全匹配和全不匹配之间转换（使顶层的一对对角交换，底层同样）。当你手中的魔方不处于这个状态时，这有一个公式可以交换底层的一对对角，同时交换顶层的一对相邻的角块：

　　R'FR' - 使4个目标角块移到B层
　　B2 - 交换！
　　RF'R - 返回

　　在这种情况下，可以非常高效的暂时打乱G2，在这一步骤的结尾，又返回到G2状态集中。这个公式会交换DF、DB、UB三对角块，而不会影响到在UF处的角块对。当你在寻找那些匹配或不匹配的角块时，你会经常发现有一对与其它的不一样（比如另外三对都匹配了，只有一对不匹配）。当你找到这一对并把它拿在UF的位置，然后做上面那个公式，就会使所有角块相协调。

　　接下来开始处理棱块，这就没什么特别之处了。棱块也是位于几个环之中，魔方总共有12个棱，分为3个环。中层的棱块在步骤2中已经做好了，而且也不会再离开它们的环。所以现在，我们只有UD两层的8个棱块需要处理。我们要做的是把白色的棱移到白色那一侧（前/后，这里白色泛指白、黄），把绿色的棱移到绿色的一侧（左/右）。处于错误位置的棱块的数目一定是偶数。最简单的公式是把绿色那一侧的两个棱与白色那一侧的两个棱相交换，绿色那一侧的两个棱必须放在底层（DL、DR），而白色那一侧的两个棱必须放在顶层（UF、UB）。然后做：

　　D'
　　M2（M是被L和R层夹在中间的层）- 交换！
　　D

　　这应该不需要解释了。像步骤1一样，如果你遇到了只有两个不正确的棱，那你可以很容易的把它变成4个。
　　在这个步骤的末尾，你应该看到，在每个面上都只有它自身的颜色和它相对面的颜色。

**步骤4**

　　魔方现在只用180度旋转就可以还原了。当然，如果我们能看出一些明显的捷径来，也可以用180度旋转以外的操作。

　　首先，用180度旋转来还原角块。先找到一个面，把两个角块连在一起，那么这个面上的另两个角块就会自动连在一起（如果你步骤3做对了的话）。然后把两对角块移到一个面，另外4个角块自然会自动复原（如果你步骤3做对了的话）。

　　接着还原棱块，这有两个容易理解的简单公式：
　　F2R2 F2R2 F2R2 - 交换不同环中的两对棱块，其它的块不受影响。
　　F2 M2 F2 M2 - 交换同一环中的两对棱块，第二个F2会把其它的块复原。

　　运用这两个公式及它们的一些变化，就能够还原所有的棱。

　　第一个公式的变化包括：
　　R (F2R2 F2R2 F2R2) R'
　　L2B2R (F2R2 F2R2 F2R2) R'B2L2

　　第二个公式的变化包括：
　　F2 M F2 M' （将两对棱重叠在一起，这样就能交换三个棱）
　　F (F2 M2 F2 M2) F'

CUBE SOLVED
魔方还原完毕

Ryan
Copyright © 2003 Ryan Heise

[ 本帖最后由 noski 于 2008-11-25 00:39 编辑 ]

作者: noski 时间: 2008-3-24 15:05:30

OK，先发这些，其它方法会陆续整理出来。
从这两封E-mail中，我们会发现这是一个很有意思的方法。
现在国内鲜有最小步还原的理论，也似乎没有人玩，我希望能为这一玩法的推广做一点点贡献。

注：FMC，Fewest Moves Challenge。
World Record：28步。

这似乎只是很多方法中的一种，我还有一丝疑惑，要尝试一下，看看它到底是FMC，还是SpeedCubing..

[ 本帖最后由 noski 于 2008-11-25 00:39 编辑 ]

作者: bfans2004 时间: 2008-3-24 17:15:51

提示: 作者被禁止或删除内容自动屏蔽

作者: 一叶知秋 时间: 2008-3-26 23:05:33 标题: 回复 2# 的帖子

精辟！独到！终于看到有实际意义的最少步还原方法了！

谢谢楼主

作者: 大烟头 时间: 2008-3-27 09:16:43

魔方比赛中就有设一项最少步的比赛，参赛的人只能备一张纸与一支笔，不许转动魔方，谁算出的步最少就是冠军，这个项目目前的WCA纪录好象是28步。
 
魔方吧论坛虽然有设这个“最少步”的分区，但基本上都没人研究这个项目，包括理论区的几位大佬。此贴象是一把锁匙，指引大家走入“最少步算法”的大门。
 
 
谢谢楼主提供分享。<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/handshake.gif" border=0 smilieid="17"> 
 
加精、加固、加亮！
 
 
 
 
 
 

[ 本帖最后由大烟头于 2008-3-27 09:22 编辑 ]

作者: 雾沁 时间: 2008-3-27 09:27:46

看不懂...
此时的我果然还是只能呆“菜鸟入门”及“FCOP”

作者: noski 时间: 2008-3-27 10:11:17

谢谢大家的支持和帮助，有什么好资料我还会再拿回来分享的

作者: 一叶知秋 时间: 2008-3-27 19:34:30

原帖由 大烟头 于 2008-3-27 09:16 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=103597&ptid=7091" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 魔方比赛中就有设一项最少步的比赛，参赛的人只能备一张纸与一支笔，不许转动魔方，谁算出的步最少就是冠军，这个项目目前的WCA纪录好象是28步。

不许转动魔方

规则不是说可以自带三个魔方的吗？应该可以试转的吧

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
又去比赛规则里看了看：

E3）参赛者可以使用以下物品纸和笔（均由裁判提供）、三个魔方（自备）、不限颜色的贴纸（自备）。

还提到了贴纸，难道是不可以转动魔方，只能在魔方上面贴帖纸？
一片茫然……

[ 本帖最后由一叶知秋于 2009-1-1 20:41 编辑 ]

作者: ggglgq 时间: 2008-4-3 11:17:06

         应该可以试转的！请参考： <A href="http://bbs.mf8-china.com/viewthread.php?tid=6905&extra=page%3D2&page=3">附则E 最少步数还原</A>  22 楼。 
<A href="http://bbs.mf8-china.com/viewthread.php?tid=6905&extra=page%3D2&page=3">http://bbs.mf8-china.com/viewthread.php?tid=6905&extra=page%3D2&page=3</A>
 E1）标准规则见文章 A（速拧）。最少步数还原的附加规则如下所述：
E2）最少步数还原的程序： 　　　　·E2a）裁判把一个打乱算法交给所有参赛者，裁判启动秒表并说“开始”。 　　　　·E2b）参赛者有 60 分钟的时间以尽可能少的步数解决这个打乱算法 　　　　·E2c）在60分钟结束时，参赛者必须把他的解法符号清晰的写下来交给裁判，符号写法参考第十二章。 　　　　·E2d）衡量解法长度的步数单位是“半转”，转动 180 度算作两步。 　　　　·E2e）参赛者的解法不能和打乱算法有任何的关联，否则将被取消本次还原的资格 　　　　·E2f）参赛者必须清楚的说明他的解法。
E3）参赛者可以使用以下物品纸和笔（均由裁判提供）、三个魔方（自备）、不限颜色的贴纸（自备）。 　　　　·E3a）如果使用其他物品，将被取消本次还原的资格。

作者: ggglgq 时间: 2008-4-3 11:23:43

 
            （各类）魔方状态的“最少步数”，严格意义上讲，绝大多数只能用计算机 编程才能实现，其算法极其深奥讲究（一般遍历算法是不可取的和不可能实现的）。       现在人们所说的“最少步数”玩法，多是指“手工最少步数还原”，要求 不高，多是“公式”堆砌而成的，很少能实现真正意义上的“最少步数”。         <IMG src="http://bbs.mf8-china.com/attachments/month_0804/20080403_3990676a6445d3999396LeqyLjiBKVti.png" border=0>              上述“[FMC]状态集转换法”原理是这个“N 阶段算法构想图”。人们所说的 “最少步数”玩法要在 60 分钟的时间尽可能贴近“红色最佳路线”，非常困难！ 因为这个算法就是类似“利用人脑来实践计算机算法的理论。”，随机因素很大， 呵呵！           Cube Explorer 用的是“两阶段算法”，这是人脑根本无法实践的算法。对于 这个“红色最佳路线”的不懈追求，是各国魔方爱好者的梦想，希望大家共同努力！

作者: Cielo 时间: 2008-4-12 14:04:25

呀居然才看到这个帖子，看来我很久没来最少步区了…… 顶！ 那两封信里也提到了要提高速度~这比较诡异~因为感觉用这种方法速拧肯定不会太快吧。嗯里面提到的状态集的想法非常好<img smilieid="1" src="http://bbs.mf8-china.com/images/smilies/default/smile.gif" border="0"> 不知道28步的世界记录是用什么方法算出来的哦，好奇啊！ 

[ 本帖最后由 Cielo 于 2008-4-13 03:38 编辑 ]

作者: 我差我存在 时间: 2008-4-18 14:47:11

厉害
顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶

作者: hzhenr 时间: 2008-5-26 23:53:10

提供的纸和笔能不能用来当草稿纸计算的？还是专门用来写答案的？

作者: oyyq99999 时间: 2008-5-31 13:18:20

原帖由 ggglgq 于 2008-4-3 11:17 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=106833&ptid=7091" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
        应该可以试转的！请参考：附则E 最少步数还原  22 楼。
http://bbs.mf8-china.com/viewthread.php?tid=6905&extra=page%3D2&page=3
E1）标准规则见文章 A（速拧）。最 ...

180度算1步，内层才算2步

作者: chuan1392010 时间: 2008-7-31 15:45:03

努力的看，可是还是看不懂

作者: earthengine 时间: 2008-8-23 21:58:55

我正在尝试这种方法，说一下心得。

目前我对于第一阶段（棱块定向）已经得心应手。这一阶段的目标是将所有棱块的方向定死，使它不能被以后的转动改变。难点是比较眼花，需要培养一种从纷纭复杂的状态判断棱块方位的能力。

任何两个对面的颜色，直到最后一个阶段开始之前都是认为相同的。因此你可以认为正在转一个三色魔方。

第一阶段将左面和右面作为垃圾池，凡是有方向不对的棱块，一起挪到这两面之一，然后在该面上转动90度消掉方向的变化。我可以提供一个快速判断棱块是否已经定向的方法。任何一个棱块，它的两个色片总是会在两个相邻的面上。这两个色片中，至少有一个不是在左右两面。凡是这样的色片，要是颜色和所在面的中心块相同，那就算正确了。要是不同，那么可能和另一个色片所在那个面（注意排除左右面）相同，这时候它的方向是错误的。如果两种假设都不成立，那么会有一个色片跟左右面颜色相同，这时候标准是该色片不能在左右面。

作者: bskypm2000 时间: 2009-8-29 00:54:00 标题: 搞出来了，不熟，得好长时间

G1棱块和G2棱块应该可以一起做，G2角块和G3角块也应该可以一起做。剩下的一起。

不知道有没有人整理出简化公式。

作者: aubell 时间: 2009-9-21 12:49:53

这么好的文章，我居然现在才看到！
真是相见恨晚啊！！！！！

作者: Greenoracle 时间: 2009-9-21 13:58:27

哈哈，原来早有介绍这个方法的贴，没注意。

作者: dongzhuimu 时间: 2009-11-21 21:18:05

好深奥菜鸟看不懂

作者: 龙魔 时间: 2010-3-2 13:06:19

俺就是要学看不懂的······

作者: top0831 时间: 2010-3-14 12:55:13

很感兴趣！也说明我们中国的教育出了大问题！没有创新也没有独辟蹊径。不如解放前的兼容并蓄了！

作者: zykey 时间: 2010-3-22 16:25:39

这么多的理论看的我。。。。。。。。头疼啊......................................

作者: 龙魔 时间: 2010-6-22 00:45:49

今天俺又来寻觅旧路，对TM大致有哦了解，俺还会来的

作者: 假木瓜 时间: 2014-1-18 14:25:41

速拧是不行的，我现在最快才2：09.172。

作者: 假木瓜 时间: 2014-1-18 14:28:41

还有，得到较少步数的解决方案的几率确实很低。

作者: 武铭 时间: 2014-2-6 20:02:52

不明觉厉

作者: 虚梦年华 时间: 2014-3-29 16:59:11

学了很久才学会……个觉得人降群法有点麻烦……无论是速拧还是最少步都有点鸡肋，如果能整理出一份完整的降群公式表，降群应该还是很不错的……感觉降群的第一步和ZZ差不多，往后越做越麻烦……不过总的来说，只要掌握了降群的思想，就很好学了。

作者: 与魔为友 时间: 2014-8-25 11:40:12

好深奥!!!我是菜鸟。。。。看不懂！。。

作者: 黄克元 时间: 2014-11-7 19:16:28

好复杂的说……状态集是啥

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)