魔方吧·中文魔方俱乐部

标题: 回到最初，从52步的 Thistlethwaite 开始 [打印本页]
作者: aubell    时间: 2011-2-6 14:59:16     标题: 回到最初，从52步的 Thistlethwaite 开始

引子：
人们已经证明了20步是足够的。
目前，有很多程序都可以做到20步还原。
大多数能在20步以内还原的程序都使用2-phase算法。
2-phase算法来源于Thistlethwaite算法。
Thistlethwaite算法是最初。
现在，打算回到最初，看看Thistlethwaite老先生是如何做的。

准备用这个帖子详细的分析下面这个页面
http://www.jaapsch.net/puzzles/thistle.htm

希望温故知新。
那个页面的内容将陆续copy过来。
一点一点分析。

千里之行，始于足下。欢迎大家支持。

（这种一点点渐进的方式，更有利于及时发现和更正错误，
欢迎您指出纰漏之处。
）

先对这种方法有感性的认识；请尝试第4楼，第5楼的两个还原。
怕看密密麻麻的字的朋友，就看公式吧。

第三页慎入，因为图片太多，打开很慢。

[ 本帖最后由 aubell 于 2011-2-16 20:31 编辑 ]
作者: aubell    时间: 2011-2-6 15:01:15

Thistlethwaite's 52-move algorithm
Thistlethwaite的52步算法

（先说这个方法，最初是为计算机设计的，后来，有人（Ryan Heise）改进了，人类也可以用了。最早的中译是“状态集转换法”。查阅相关的帖子可以找到。
http://bbs.mf8-china.com/viewthread.php?tid=7091&highlight=%D7%B4%CC%AC%BC%AF
老先生的名字实在很长，很不好记，您有什么简单的优雅的记忆方法，可以分享给大家吗？或者优雅的音译，就像“梵阿铃”这样优雅的？）


Morwen B. Thistlethwaite is a mathematician who devised a clever algorithm for solving the Rubik's Cube in remarkably few moves. It is a rather complicated
method, and therefore cannot be memorised. It is only practical for computers and not for humans. This algorithm is rather important from a theoretical
standpoint however, as it has long been the method with the fewest number of moves.
老先生是一位数学家，他发明了一种巧妙的算法来解魔方，而且，步数很少！这种方法有点复杂，因此无法记忆。仅供电脑使用，人类不可用。从理论上讲，这种方法非常重要，因为，长期以来，这种方法都被用来寻找最少步数。
（现在，这种方法人类也可以用了，但效率自然无法同计算机抗衡。）

Thistlethwaite's method differs from layer algorithms and corners first algorithms in that it does not place pieces in their correct positions one by one.
Instead it works on all the pieces at the same time, restricting them to fewer and fewer possibilities until there is only one possible position left for
each piece and the cube is solved.
老先生的方法同逐层或角先法很不相同，不同之处在于，这种方法不是把方块一个一个地放回。而是同时对所有的方块进行操作，逐步限制它们可能出现的位置，直到每个方块只能出现在一个位置的时候，魔方就被还原了。

The way it does this is by first doing a few moves until a position arises that can be solved without using quarter turns of the U and D faces (though half
turns of U and D are still needed). It then proceeds to solve the cube without using U or D quarter turns by first moving to a position that does not need
quarter turns of the F, B faces either. With these further restrictions a position is arrived at that does not need any quarter turns at all, and can hence
be solved by half turns only. The cube then indeed gets solved using half turns only.
这种方法先做一些简单的操作，使得魔方进入这样一种状态：不需要U、D面的1/4周旋转（1/2周旋转是需要的）也可还原。然后继续，不使用U、D面的1/4周旋转，使得魔方进入这样一种状态：也不需F、B面的1/4周旋转就可还原的状态。进一步，不需要所有的1/4周旋转，然后仅用1/2周旋转就可以还原了。

（原始方法限制的顺序，同现在的习惯不同，现在，最常见的是先限制F,B,然后限制L,R,最后限制U，D。为什么会这样呢？大约那个时候还不追求“速度”，没有“手法”、“公式”之类，只求观察方便。而且，对计算机来说，6个面没有什么不同，计算机做“6色底”比人类强大。）


These four stages are quite complicated, since they use large look-up tables for all the positions at each stage. The table below shows the numbers involved:
这四个步骤相当复杂，因为每一步都有一个巨大的表要查。下面的表显示用到的数据：

Group # positions  Factor
G0=<L, R, F, B, U, D>4.33·10192,048(2[sup]11[/sup])
G1=<L, R, F, B, U2,D2>2.11·10161,082,565(12C4 ·37)
G2=<L, R, F2,B2,U2,D2>1.95·101029,400( 8C4[sup]2[/sup] ·2·3)
G3=<L2,R2,F2,B2,U2,D2>6.63·105663,552(4!5/12)
G4=I1

（以上的数字是如何计算的：
待续... ...）

Mathematically speaking, this is a sequence of nested groups, and each stage of the algorithm is simply a look-up table showing a solution for each element in the quotient coset space. The last column shows the order of these coset spaces, i.e. the size of the look-up tables used.

（到这里，发现上面的一段没法翻译了，因为群论的术语不知道该怎么翻！唉，大致就是每一步要查的表的大小了了。请高手告诉一下，那些术语该如何翻译呢？陪集？秩？陪集空间？虽然这个方法是基于群论的，大概也可以避开群论，只用魔方的术语吧。）


The first stage has a factor of 2,048=2[sup]11[/sup]. This corresponds to the fact that this stage fixes the orientation of the edges; it is impossible to flip edges if only half turns are allowed on the U, D faces, but otherwise the pieces can be put in any normal position with this restriction.
第一个因子：2048=2的11次方。这对应着第一步要翻正棱的方向。不使用1/4转的U、D是不可能翻正棱块方向的，但其它（诸如棱的位置、角的方向、角的位置）都可完成。

The second stage has a factor of 37 *12!/(8!4!). This corresponds to the fact that this stage fixes the orientation of the corners, and places the middle layer edges into their slice. It is fairly easy to see that if you are only allowed half turns on the F,B,U,D faces together with any turns on the L, R faces, then the left and right faces will never have more than two colours, and the middle edge pieces will never leave their slice or be flipped. In fact, those restricted moves can solve any position under those conditions.
第二个因子，3的7次方乘以12选4，对应着角的方向以及中层棱的位置。很容易看出来，如果只用F,B,U,D的1/2周旋转以及L,R面的任意旋转，左右两个面就只有两种颜色，并且中层的棱不会离开中层，也不会被翻转方向。这些受限的操作能够还原有限的状态。

The third stage has a factor of [8!/(4!4!)]2 *2*3. This corresponds to the fact that the edges in the L and R faces are placed in their correct slices, the corners are put into their correct tetrads, the parity of the edge permutation (and hence the corners too) is made even, and the total twist of each tetrad is fixed.
第三个因子，8选4的平方乘以6.这对应着处在LR两个面上的棱回到对应的中层上，角回到对应的组中，以及单独的棱对换（角对换也包含），每组方向都正确。
（第一个8选4，是从8个棱中，选4个，进入对应的中层，如E层；第二个8选4是从8个角中选4个，进入对应的组，最后的6是那四个角的排列方式。话说为什么不是4!，因为每4种状态中就有一种是G3群的。）

The final stage finally solves the cube.
最后就是解魔方。

The following table shows the number of moves each stage needs.
下面的表显示每一步骤所需要的步数：
1234total
Original algorithm:71315 17 52
Improved algorithm: 7131515 50
Best possible:710131545

这个表显示了这种方法在改进过程中的进步，从52步逐渐进步到45步.
(这个不值得夸耀，因为现在人类选手用CFOP或者组块的方法，也能比较轻松的少于这个数字；但值得学习，因为
CubeExplorer使用的2-phase起源于这里。)

[ 本帖最后由 aubell 于 2011-2-6 18:21 编辑 ]
作者: aubell    时间: 2011-2-6 15:02:20

To keep the size of the lookup tables down, Thistlethwaite used simplifying preliminary moves which is why the number of moves he needed is sometimes more than the best possible (the 'diameter' of the quotient spaces). His students first improved the algorithm by completely analysing the square group, thus reducing it to 50 moves. Later each stage was fully computed, for a 45 move solution. In 1991 Hans Kloosterman reduced that to 42 moves by using slightly different stages 3 and 4.

为了减小表的尺寸，Thistlethwaite老先生使用了一些简单的预操作，这就是他的步数有时比最好可能性多的缘故。他的学生完整的分析了平方群，就把这个数字缩减到了50步。以后，每一个步骤都完全算过了，可以在45步完成。1991年，Hans Kloosterman在第3和第4步使用略为不同的技术，把步数缩减到了42步。

Through extensive calculations, Mike Reid has shown that going from G0 directly to G2 can be done in 12 moves, and from G2 to G4 in 18 moves. When combining these, the 30-move cases can be avoided, so it has been proved that 29 moves is always sufficient to solve the cube. More recently other techniques have allowed computers to verify that God's Algorithm is 20 moves in the worst case.

通过彻底的计算，Mike Reid发现，从G0到G2可以在12步以内完成，从G2到G4可以在18步以内完成，合并以后，30步是可以避免的，解魔方实际29步就足够了。最近，其它技术使得计算机验证了，20步可以解决最坏的情况。
参见http://cube20.org


Ryan Heise has developed a way of solving the cube based on Thistlethwaite's algorithm. He splits stages 2, 3 and 4 into two steps each (corners and edges separately) in order to make it possible for a human being to memorise.
Ryan Heise开发了一种方法，基于Thistlethwaite方法。把2，3，4三个步骤都拆成2步（角与棱分开处理），使得人类能够记忆，使用。参见http://www.ryanheise.com/cube/human_thistlethwaite_algorithm.html


David Singmaster has made scans of Thistlethwaite's printouts, and I converted them to text. Below is a reproduction of those papers, as accurate as I can make them. It consists of
1. Covering letter, 1 page
2-4. General Instructions, 3 pages
5-10. Stage 2 tables, 6 pages
11-18. Stage 3 tables, 8 pages
19-25. Stage 4 tables, 7 pages
26. Detailed example, 1 page.

David Singmaster扫描了Thistlethwaite打印输出的文件，jaap把它们转成了文本。下面是那些纸张的复件，jaap做的尽量精准。由以下部分组成
1.封面的信
2-4.总体介绍
5-10.第二步骤的表
11-18.第三步骤的表
19-25.第四步骤的表
26.详细的例子

（总共26页，我看这26页的时候，总是怀着无比尊敬的心情。因为这个算法之于计算机解魔方，就好比lisp之于计算机程序设计，可谓是鼻祖。为什么要重复学习一遍4步骤呢？一方面，加深对群论的理解；一方面，表达对Thistlethwaite前辈的尊敬。）


26 Queens Road, Loughton, Essex. 13 July 1981. Dear Thank you for your letter asking for a copy of my 52-move strategy for solving Rubik's Cube. Please find
enclosed the following:- (i) General instructions and description (3 pages); (ii) Tables for Stage 2 (computer print-out); (iii) Instructions and table for
the first part of Stage 3; (iv) Tables for the latter part of stage 3 (7 typewritten pages); (v) Tables for Stage 4 (7 pages of computer print-out,
photocopied). I should perhaps point out that this strategy isn't easy to perform (even John Conway finds it quite hard!), for two reasons: first, only one
representative of each symmetry class is given in the tables; second, I have given only the barest documentation. I hope that a fuller description will be
forthcoming at some stage. On reading the bottom of page 2 of the General Instructions, you will note that in fact Stage 2 requires two sets of tables. I
have omitted to send you the second of these, because they are bulky, and only save one move! I hope you will excuse this liberty. One can always get
FU,FD,BU,BD into the UD-slice (the middle horizontal slice) in at most five moves in G1. As an example of the strategy at work, consider the position where
the four upper corners are twisted clockwise, the four lower corners are twisted antlclockwise, and all twelve edges are flipped. Then the cube is restored
by:- Stage 1 DBFUR'L'D Stage 2 L2F2D2F | L2R2F'R'BR2B'R'B' Stage 3 L2B2 | U2LU2F2L2F2L'B2LB2L' Stage 4 R2U2 | R2D2F2U2B2D2F2B2L2B2L2B2 Yours sincerely,
Morwen B. Thistlethwaite.


（这个是封面的信。开头是发件人的地址，日期。日期是1981年，很古老了。那时，图形界面还不流行，也不知道 Thistlethwaite先生用的是什么操作系统。总之，很了不起了。）

感谢你写信来要我的52步解魔方策略。请找到以下的这些:-
(1)总体介绍（3页纸）
(2)第二步骤的表（计算机打印的）
(3)第三步骤的介绍和部分表
(4)第三步骤的表，后一部分(7页打印纸)
(5)第四步骤的表，(7页打印纸,影印的)。
Thistlethwaite指出，这一策略不是那么容易实现的（尤其是John Conway指出，真的很难！）有两个原因：第一，在对称的类型里，只给出了一个代表；第二，只给出了单纯的文档。Thistlethwaite期待，某个时候会有完整的描述出现。在阅读第二页的总体介绍以后，你会发现，第二步需要两个系列的表。省略了一个，只给了第二个，因为那太庞大，而且只存储一步移动！希望你能原谅。最多5步，使用G1群的移动就可以把FU,FD,BU,BD四个棱块集中到UD之间的一层（水平中间层）。
作为这种策略的一个例子，假定这样一种状态：顶层的四个角处于顺时针旋转的位置，底层四个角处于逆时针旋转的位置，所有棱处于翻转的位置。那么，可以按照如下次序还
原:-
  1. 第一步骤:DBFUR'L'D
  2. 第二步骤:L2F2D2F  | L2R2F'R'BR2B'R'B'
  3. 第三步骤:L2B2 | U2LU2F2L2F2L'B2LB2L'
  4. 第四步骤:R2U2 | R2D2F2U2B2D2F2B2L2B2L2B2
复制代码
最后是 Thistlethwaite 的署名
（这个状态的打乱公式:
  1. R' B2 D2 B2 D2 U B' L' F L2 B2 F R F' D U R2 F' L F2  (20f)
复制代码
，使用CubeExplorer计算），还原过程如上。

（aubell准备给出一个完整的描述。并且制作完整的可以手动查的表。而且顺序调整成现代的顺序，先限制FB，然后限制LR，最后限制UD，以期同
手动的方法相适应。
那个年代，通讯技术不发达，全用纸打印，不绿色环保啊。）

[ 本帖最后由 aubell 于 2011-2-6 21:42 编辑 ]
作者: aubell    时间: 2011-2-6 15:03:45

做一个映射，把上面的打乱公式和还原公式都变成现代的习惯：
L R F B U D ==> D U R L F B
映射，把所有的L改写成D,R改写成U,F改写成R，类推。

打乱公式：
  1. U' L2 B2 L2 B2 F L' D' R D2 L2 R U R' B F U2 R' D R2
复制代码

还原公式：
  1. 1. B L R F U' D' B
  2. 2. D2 R2 B2 R D2 U2 R' U' L U2 L' U' L'
  3. 3. D2 L2 F2 D F2 R2 D2 R2 D' L2 D L2 D'
  4. 4. U2 F2 U2 B2 R2 F2 L2 B2 R2 L2 D2 L2 D2 L2
复制代码

[ 本帖最后由 aubell 于 2011-2-6 22:59 编辑 ]
作者: aubell    时间: 2011-2-6 15:06:47

文章尾部的例子，转换成现代的形式。

打乱
  1. U B' R' B' U2 L2 U B' R B R2 D' L2 D2 R2 F2 U F2 B2 D2  (20f)
复制代码


还原
  1. 1. R D U' B2 L2 F
  2. 2. R2 B2 D U' R U2 R L2 U L' U2 L U L
  3. 3. D' F2 U' F2 B2 U2 B2 D' R2 D B2 D'
  4. 4. D2 U2 L2 U2 R2 U2 B2 F2 L2 F2 U2 F2 U2 F2
复制代码

[ 本帖最后由 aubell 于 2011-2-6 23:45 编辑 ]
作者: aubell    时间: 2011-2-6 15:08:33

page 1 THE 45-52 MOVE STRATEGY Introduction. Let G= <L,R,F,B,U,D> , G1= <L,R,F,B,U2,D2> , G2=
<L,R,F2,B2,U2,D2> , G3= <L2,R2,F2,B2,U2,D2> . The plan is to manoeuvre down through the chain
G=G0> G1> G2> G3> 1. One gets from Gi to Gi+1 by using moves in Gi only. In its shortest form
this strategy would be executed with the help of a computer, in which case I conjecture only
45 moves would be needed, but here I have sacrificed 7 moves in order that there should be no
need for a computer. With a few more pages of tables, the figure 52 could be reduced to an
intermediate figure of, say, 49. I intend to do this shortly! The indexes of the chain of
subgroups are 2048, 1082565, 29400, 663552, but these figures are considerably reduced by
considering symmetries. The reader may check that these indexes multiply together to give the
order of G. The accompanying tables are broadly classified according to corner positions, and
in detail according to edge positions. The words listed actually produce the positions under
consideration, so the restoring moves are the inverses of these. In order to be able to use
the tables it is necessary to understand the basic characteristics of the groups G1, G2, G3,
so the necessary facts are presented below. Getting into G1. This involves edge pieces only,
and is easy, for which reason no tables are given. An edge piece is BAD if in taking it home
an odd number of quarter-turns of U and D faces is needed; otherwise it is GOOD (note that
badness is well-defined). The reader may quickly work out a rule of thumb for deciding
whether a piece is GOOD or BAD. Now quarter-turns of either U or D faces convert BAD pieces
to GOOD and vice versa; other moves have no effect. Therefore to make all edge pieces GOOD,
move groups of them to U or D face avoiding quarter-turns of U or D, and then cure them by
performing a quarter-turn of U or D. For example, if all twelve are BAD, DBFUR'L'D will cure
them all!

第一页 45-52步策略介绍
令 G=<L,R,F,B,U,D>,G1=...,G2=...,G3=...计划这样降下来：
G=G0>G1>G2>G3>1. 从Gi进入Gi+1，仅使用Gi规定的操作。这种方法最简短的形式，用电脑来算的话，估计
45步足够了，但这里，牺牲7步，电脑其实不需要。使用几页纸的表，52可以缩减到49.子群链的indexs分
别是：2048,1082565,29400,663552,但显然，这些数字可以用对称来减小。读者可以检查，这些数乘起来
，正好是群G的秩。陪集表用角的位置来分类，用棱的位置来详细描述。列出的表是思考的过程，因此，还
原的顺序要颠倒过来。为了能使用这些表，要理解群G1,G2,G3的基本属性，因此，下面介绍必要的情况。

进入G1
这一步仅涉及到棱，并且很容易，因此，没有表给出。“错误”的棱是指需要奇数次的U与D操作才能返回
原位的；其它情况就是“正确”的。（注意：“错误”的方向有了明确的定义。）读者很容易发现确定一
个棱的“好坏”的准则。这样，90度的U或D旋转就用来把“坏”棱变“好”，“好”的变“坏”；其它操
作没有影响。因此，要把所有的棱方向变“好”，只要不使用奇数次的U,D旋转，把它们集中到U面或者D面
上，然后做一个1/4周的U或D面的选装。例如，如果所有的棱都是“坏”的，这个操作可以把它们都翻正：
DBFUR'L'D。

（现代的习惯，先限制F,B；也就是把G1定义为<F2,B2,U,D,L,R>。在定义“错误的棱向”的时候，用奇数
次的FB；翻转棱的状态时，是集中在F,B面，然后用奇数次的F,B翻转。也就是说：如果12个棱的方向都不
正确，翻转公式可以是：
B L R F U' D' B 。
在定义G1,G2,G3时，限制的顺序不同，就会产生“优先级”不同的感觉。先限制F,B产生的效果，同某些盲
拧方法对棱向的定义是一致的。
）

[ 本帖最后由 aubell 于 2011-2-7 01:20 编辑 ]
作者: 1900    时间: 2011-2-6 15:09:47

果断沙发！顶一个啊！！
作者: oyyq99999    时间: 2011-2-6 15:21:36

据说不就是四阶段么。。。
作者: LOVEGARFIELD    时间: 2011-2-6 15:22:48

支持LZ，前排围观，先顶了！
作者: 眺望    时间: 2011-2-6 15:24:39

多了一层  好像
作者: aubell    时间: 2011-2-6 15:31:22     标题: 回复 8# 的帖子

没错啊。就是4个阶段。假如每个阶段能平均5步，4×5也恰好20步啊！
作者: oyyq99999    时间: 2011-2-6 15:47:33     标题: 回复 11# 的帖子

这有什么好研究的。。。
作者: aubell    时间: 2011-2-6 15:55:05     标题: 回复 12# 的帖子

我要研究过以后，才能知道，有什么好研究的
开工了，支持一下吧。
作者: 极乐鸟    时间: 2011-2-6 16:26:44

支持下。。看看是什么。
作者: modgl1993    时间: 2011-2-6 17:28:00

很期待！！
看来真的是个大工程！！
顶了！
作者: 双面胶    时间: 2011-2-6 18:10:38

支持LZ，“第二排”围观，先顶了！
作者: Xwam    时间: 2011-2-6 20:56:51

这个，先支持一下了~~慢慢看~~
作者: aubell    时间: 2011-2-7 00:32:26

stage 1 -- OE           翻转棱，同现代的“手动”方法没有不同
stage 2 -- toE OC     一个中层的棱回到中层，与之平行的两个面角块方向翻正
                                这里分了两个步骤，但是同“手动”方法是有不同的。看这一句很关键：

On reading the bottom of page 2 of the General
Instructions, you will note that in fact Stage 2 requires two sets of tables. I
have omitted to send you the second of these, because they are bulky, and only
save one move! I hope you will excuse this liberty. One can always get
FU,FD,BU,BD into the UD-slice (the middle horizontal slice) in at most five
moves in G1.

只发了一个表。

注意：作者当时对G1,G2,G3,G4的定义，当时说的四个棱相当于现在说什么？
相当于在说把RF,RB,LF,LB四个棱放到FB-slice

再注意到，那个表是“生成表”，在实际的还原过程中要做“公式的逆”。
从文章末尾的例子可以看到，在查表之前，要把属于E层的四个棱停在S层上！
也就是说，那些公式的逆将把S层的棱发送的E层。
那么，那些公式本身就应该是把E层的棱送到了S层。

查表之前做OC之前，不是做E层棱回E层，而是做E层棱进入S层。
因为所有给出的公式的逆都有把停于S层方块发到E层的效果。
这个是和现代手动方法不同的地方。

[ 本帖最后由 aubell 于 2011-2-8 15:20 编辑 ]

附件: map.JPG (2011-2-8 15:07:59, 29.89 KB) / 下载次数 31
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDU1fDc1ODAyYTVlfDE3NjE4MzkxMzl8MHww

附件: stage 2 原始公式.rar (2011-2-8 15:20:40, 15.11 KB) / 下载次数 7
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDU2fDQ1OTg5YzIzfDE3NjE4MzkxMzl8MHww
作者: tm__xk    时间: 2011-2-7 00:44:15

这个..先顶顶吧..看看lz能弄出多少东西来..
作者: aubell    时间: 2011-2-7 01:30:51

这一层发问题，备忘：

1. 把那些“古代”公式，变成“现代”形式，到底有多少种不同的映射方式？
  （六个面都可以做底，四个侧面可以做F，那么，整体的变换是24种方式。加上镜面，共48种方式。
    符合特定“优先级”。优先级应该分六类。所以，每种优先类别种有8种方式可以满足。
    映射有8种。
）

2. 第二个步骤的给出的公式为何是整齐划一的9步公式？
（莫非是古代电脑的要求？）

3. 第二步查表前，把E层棱停在S层？
（因为 R和L 用来翻角，从S进入E只需简单的RL即可。）

[ 本帖最后由 aubell 于 2011-2-8 15:35 编辑 ]
作者: aubell    时间: 2011-2-7 02:14:15

page 2 Getting from G1 into G2. What has been achieved so far (although it doesn't look like it) is the

correct orientation of edge pieces! In the present stage, the same is accomplished for corners, and also

the edge pieces FU, FD, BU, BD are brought into their slice. As is well known, corners do not in general

have a natural orientation, but here, roughly speaking, we shall line them all up the same way. More

precisely, note that each corner piece has either a L-facet or a R-facet: on completion of this stage

each of these facets will lie on either the L or the R face. In fact, the same will be true of the eight

edge pieces with L or R facets, in view of the statement above regarding FU, FD, BU, BD. There are

1082565 cases to consider here, this number being the product of 3^7(total number of corner orientations)

, and 12C4 (total number of arrangements of the set {FU, FD, BU, BD} amongst the twelve edge positions).

Surprisingly, with a certain amount of practice it is possible to get through this stage in at most 17

moves without tables; the same is most certainly not true of the next stage although there are only 29400

cases. However, with a few pages of tables this figure of 17 may be reduced to 13; with a great deal more

computation, it should be possible to reduce it further to 10. To "prove" that 10 moves were sufficient,

one would run through all 10-move sequences on the computer, and check that 1082565 different cases

resulted. This would take no more than a few hours of computer time, in view of certain short cuts

available by considering symmetries. Now to business. The twist of a corner is measured by looking at its

L or R facet and observing how this has been rotated in relation to the adjacent L or R face. Note that

quarter-turns of F and B faces alter the twist of corners, whereas all other moves in the group G1 have

no effect. Now in at most 4 moves in G1 try to obtain a position the edge pieces FU, FD, BU, BD are all

in the UD-slice. If this is not possible, get them all in the U-face in at most 4 moves.

第二页 从G1进入G2 在纠正了棱的方向以后，已经前进了一大步（尽管看起来并非如此）！在这个步骤中，角的方向也

要被翻正，并且FU,FD,BU,BD四个棱也会回到它们应该在的中间层。大家都知道，角并没有所谓自然的朝向，但这里，严

格的讲，我们要让所有的角朝同样的方向。准确的说，注意：每个角块都会有L或R面的贴纸：在完成这一步以后，L或R

面的贴纸只能朝向左或右。事实上，上一步对含LR面贴纸的8个棱也是同样的效果，看FU,FD,BU,BD四个棱。这一步有

1082565种情形。这个数字是3的7次方（角的朝向）乘以12选4（中层四个棱在12个位置中的某处）得出的的。令人吃惊

的是，不用表，仅通过一定数量的尝试，这一步可以通过17步完成。下一个步骤只有29400种情形，自然不要那么多步数

。在使用几页表之后，数字17可以缩减为13；用大量计算以后，也许可以缩减到10.为了“证明”10步是足够的，你可以

在电脑上遍历所有10步长的序列，检查结果是否覆盖这1082565种状态。这可以在几小时之内完成。角的朝向是看L,R面

的贴纸是否在LR面。注意，90度F,B面的选择会翻动棱块，其余G1群操作没有影响。这样，最多用G1中4步操作，使得

FU,FD,BU,BD四个棱回到UD之间的中层。如果这些不可能。用最多4步集中到U面。

（现代的方法是：看角，看UD面的贴纸，朝向上下；UD之间的E层棱先回到E层。“古代”是看LR面的贴纸，M层的棱先回到M层。现在也知道，17步一点也不令人吃惊，因为整个魔方只要20步，如果这个步骤就用17步，其它步骤还怎么混呢？但这种方法有意思，先用公式生成所有的状态，在还原的时候，查找状态，然后把公式逆过来做。）
作者: zxy6350479    时间: 2011-2-7 02:29:35

内容看完 头晕 很复杂
作者: aubell    时间: 2011-2-7 03:02:32

page 3 Then refer to the appropriate detailed table. The words listed in these tables need to be

inverted, as mentioned earlier. Getting from G2 into G3. This is the trickiest stage theoretically, and

may be broken down for purposes of clarification into two sub-stages: first get corners into their

natural orbits, and second permute the corners within their orbits so as to obtain one of the 96 corner

permutations in the squares group (G3), while at the same time sorting out the edge pieces into their

correct slices. The table of initial moves on the first page of Stage 3 tables does part of the first of

these substages, and the detailed tables do the rest. After performing the initial moves, the set of

corners out of orbit will be one of three possibilities (modulo symmetries): (i) the empty set; (ii) the

set {1, 8, 2, 7} ; (iii) the set {1, 5} . The reader then has to calculate which coset of form G3αβ the

permutation of corners lies in, where α is one of 1, (14)(68), (24)(58), (12), (14), (24), and β is one

of 1, (18)(27), (15). Since some of these cosets are reflections of others, it was not necessary to

produce tables for all six possible values of α. The task of reflecting positions if necessary is left

to the reader. I apologise for the slightly anomalous numbering of edge positions for this stage; this

was due originally to a typing error in a programs and has stuck ever since! Getting from G3 to home. In

this final stage one uses only 180 turns. The order of G3 is 96x6912 = 663552. The tables for this stage

give words for producing each of the 6912 edge positions with corners fixed. Therefore one must first

restore the corners (in at most 4 moves), and then use the tables to restore the edges. Considerable

practice is needed to use these tables efficiently, but I have found (after considerable practice) that I

can find the desired move in about 2 minutes. One hint is that when faced with three 3-cycles, consider

the configuration of the fixed pieces. Also it pays to get to know the different sorts of 4-cycle.

第三页 现在看如何正确查表。表中列出的词要反转一下，如前面提到的。

从G2进入G3
理论上讲，这一步最富技巧性。可以分解成两个子步骤：先让角进入自然的轨道，然后在轨道内对其进行排列，以期获

得G3中96种角排列中的一种，同时，让棱进入各自所属的中间层。步骤3的第一页的表做第一步的工作，后面的表完成后

面的工作。在执行初始化操作以后，轨道外的角的集合只会出现下面3种情况：（余子对称群）（1）空集；（2）

{1,8,2,7}的集合；（3）{1,5}的集合。读者要计算商集，G3αβ,角排列处于何种状态， α是1,(14)(68),(24)(58),

(12),(14),(24)中的一个， β 是1,(18)(27),(15)中的一个。因为有些余子集同其他是反射的，所以不必要计算α的所

有六种可能。反射的位置留给读者完成。Thistlethwaite为棱的编号怪异而抱歉，因为最初的打印错误导致！

从G3到还原
最后的步骤只使用180度的旋转。G3的秩是96*6912=663552.这一步的表给出的是角固定以后，棱的6912种排列。因此，

必须先还原角（最多4步），然后使用表来还原棱。要用好这些表需要大量的练习，但Thistlethwaite发现，他大约用两

分钟就能找到期望的解法。一点提示是面对3循环，考虑固定的块。还需了解不同类型的4循环。

（翻译到这里我们知道，尽管下面有很多页的纸张，给出了长长的公式列表，但这个表是不完整的，对称变换要还自己

做。程序和数据不是截然分开的，某些程序可以是另一些程序的数据，某些数据也可以是程序。现代计算机存储和计算

的能力都变强了，分成了4个步骤的表，应该可以完整的给出了；也可以不给出表，全都计算？）

[ 本帖最后由 aubell 于 2011-2-7 03:22 编辑 ]

附件: [原始页面的txt格式] Thistlethwaite's 52-move algorithm.rar (2011-2-7 03:22:47, 17.75 KB) / 下载次数 5
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxMzA1fGIyZDkxYWU3fDE3NjE4MzkxMzl8MHww
作者: aubell    时间: 2011-2-7 03:32:12

从G2进入G3是难点。因为这里有些群论的计算。并非简单的罗列每种状态如何用公式。
这里应该也是精华所在。因为，把一个大的集合，划分成若干小的集合，这种方法
才使得20步得到证明。
四步骤解法有了很多的实现，似乎大都没有再对G2进行分类讨论，而是仰仗计算机的能力，
很暴力的进入G3，这样的实现只能说是退步。
分类讨论是一种重要的思想方法。似乎好像那个20步的证明是直接把G0给分类讨论了。
作者: 八目阿修罗    时间: 2011-2-7 03:40:25

非常感谢lz的翻译
收藏ed
作者: aubell    时间: 2011-2-7 12:37:54

现在，要开始编码了，再实现一遍Thistlethwaite方法，要使用对称，使用群论中的乘法，使用分类讨论。
制作完整的表。
得鱼忘筌，原始的表的数据就可以不用了。
作者: aubell    时间: 2011-2-7 21:17:46

按照现代约定
G0=<U D L R F B>
G1=<U D L R F2 B2>
G2=<U D L2 R2 F2 B2>
G3=<U2 D2 L2 R2 F2 B2>

下面是第一个步骤，翻棱用表。尽管这一步不需要表，为了完整，还是做了一个表。
文中提到的其它表，也尽量弄齐。只要不是太大的话。

[ 本帖最后由 aubell 于 2011-2-7 21:19 编辑 ]

附件: oe.rar (2011-2-7 21:18:04, 32.36 KB) / 下载次数 5
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxMzgwfDhkNjRjZjRhfDE3NjE4MzkxMzl8MHww
作者: aubell    时间: 2011-2-8 13:30:39     标题: 原始的扫描图片

在txt格式的文件中，似乎某些公式有误？莫非在识别转换的时候出错了？
原始的扫描图片作为参详，仔细检查一下。
打算恢复这个算法的原貌。

[ 本帖最后由 aubell 于 2011-2-8 13:38 编辑 ]

附件: mbt52_01.jpg (2011-2-8 13:31:39, 323.02 KB) / 下载次数 54
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDIyfGYyYTVmNTZlfDE3NjE4MzkxMzl8MHww

附件: mbt52_02.jpg (2011-2-8 13:31:39, 391.11 KB) / 下载次数 55
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDIzfDJjOWVjMGNhfDE3NjE4MzkxMzl8MHww

附件: mbt52_03.jpg (2011-2-8 13:31:39, 408.81 KB) / 下载次数 50
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDI0fGE5ZmVmYzIwfDE3NjE4MzkxMzl8MHww

附件: mbt52_04.jpg (2011-2-8 13:31:39, 411.56 KB) / 下载次数 57
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDI1fDAwZDljOWY5fDE3NjE4MzkxMzl8MHww

附件: mbt52_05.jpg (2011-2-8 13:31:39, 337.67 KB) / 下载次数 54
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDI2fGRhYTg2NzI3fDE3NjE4MzkxMzl8MHww

附件: mbt52_06.jpg (2011-2-8 13:33:25, 448.17 KB) / 下载次数 51
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDI3fDhlNDI0YjJkfDE3NjE4MzkxMzl8MHww

附件: mbt52_07.jpg (2011-2-8 13:33:25, 423.12 KB) / 下载次数 50
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDI4fDI1NTcyOGRkfDE3NjE4MzkxMzl8MHww

附件: mbt52_08.jpg (2011-2-8 13:33:25, 419.42 KB) / 下载次数 50
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDI5fDNjYzY4NTdkfDE3NjE4MzkxMzl8MHww

附件: mbt52_09.jpg (2011-2-8 13:33:25, 425.19 KB) / 下载次数 59
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDMwfGZlZjUxMDk3fDE3NjE4MzkxMzl8MHww

附件: mbt52_10.jpg (2011-2-8 13:33:25, 180.57 KB) / 下载次数 50
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDMxfDQ5MGU4Nzc3fDE3NjE4MzkxMzl8MHww

附件: mbt52_11.jpg (2011-2-8 13:34:33, 263.42 KB) / 下载次数 71
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDMyfDFkNGZiOGI0fDE3NjE4MzkxMzl8MHww

附件: mbt52_12.jpg (2011-2-8 13:34:33, 408.68 KB) / 下载次数 51
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDMzfGNhMmQ1ODBkfDE3NjE4MzkxMzl8MHww

附件: mbt52_13.jpg (2011-2-8 13:34:33, 501.46 KB) / 下载次数 47
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDM0fGUzMjVhZGI1fDE3NjE4MzkxMzl8MHww

附件: mbt52_14.jpg (2011-2-8 13:34:33, 420.29 KB) / 下载次数 60
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDM1fGQ3ZDcwNzgzfDE3NjE4MzkxMzl8MHww

附件: mbt52_15.jpg (2011-2-8 13:34:33, 380.87 KB) / 下载次数 51
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDM2fGRkOTc4MDBmfDE3NjE4MzkxMzl8MHww

附件: mbt52_16.jpg (2011-2-8 13:38:11, 419.73 KB) / 下载次数 65
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDQxfDRkYTUxODMwfDE3NjE4MzkxMzl8MHww

附件: mbt52_17.jpg (2011-2-8 13:38:11, 418.19 KB) / 下载次数 64
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDQyfDI3Yzg0OTk3fDE3NjE4MzkxMzl8MHww

附件: mbt52_18.jpg (2011-2-8 13:38:11, 256.87 KB) / 下载次数 59
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDQzfGJmN2NkMDdjfDE3NjE4MzkxMzl8MHww

附件: mbt52_19.jpg (2011-2-8 13:38:11, 336.23 KB) / 下载次数 57
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDQ0fGM2NThlY2YxfDE3NjE4MzkxMzl8MHww

附件: mbt52_20.jpg (2011-2-8 13:38:11, 210.37 KB) / 下载次数 54
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDQ1fDE3YTE3YjI3fDE3NjE4MzkxMzl8MHww

附件: mbt52_21.jpg (2011-2-8 13:38:11, 216.36 KB) / 下载次数 52
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDQ2fDM3ZmNiZTBifDE3NjE4MzkxMzl8MHww

附件: mbt52_22.jpg (2011-2-8 13:38:11, 254.29 KB) / 下载次数 42
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDQ3fDZlNWE0ZDFlfDE3NjE4MzkxMzl8MHww

附件: mbt52_23.jpg (2011-2-8 13:38:11, 380.55 KB) / 下载次数 48
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDQ4fGNjMDEzZGYzfDE3NjE4MzkxMzl8MHww

附件: mbt52_24.jpg (2011-2-8 13:38:11, 355.12 KB) / 下载次数 46
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDQ5fGY0NTBmOWNjfDE3NjE4MzkxMzl8MHww

附件: mbt52_25.jpg (2011-2-8 13:38:11, 422.38 KB) / 下载次数 54
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDUwfGMzOWNjY2ZjfDE3NjE4MzkxMzl8MHww

附件: mbt52_26.jpg (2011-2-8 13:38:11, 586.09 KB) / 下载次数 53
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTMxNDUxfDA2N2JiMGM5fDE3NjE4MzkxMzl8MHww



欢迎光临 魔方吧·中文魔方俱乐部 (http://www.mf8-china.com/) Powered by Discuz! X2