回到最初，从52步的 Thistlethwaite 开始

aubell

引子：
人们已经证明了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

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·1019	2,048	(211)
G1=<L, R, F, B, U2,D2>	2.11·1016	1,082,565	(12C4 ·37)
G2=<L, R, F2,B2,U2,D2>	1.95·1010	29,400	( 8C42 ·2·3)
G3=<L2,R2,F2,B2,U2,D2>	6.63·105	663,552	(4!5/12)
G4=I	1

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

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¹¹. 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.
下面的表显示每一步骤所需要的步数：

	1	2	3	4	total
Original algorithm:	7	13	15	17	52
Improved algorithm:	7	13	15	15	50
Best possible:	7	10	13	15	45

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

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

aubell

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

做一个映射，把上面的打乱公式和还原公式都变成现代的习惯：
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

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

打乱

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

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

果断沙发！顶一个啊！！

oyyq99999

据说不就是四阶段么。。。

LOVEGARFIELD

支持LZ，前排围观，先顶了！

眺望

多了一层  好像