非专业分析KCube

aubell

目前，Kociemba是我们学习最少步数时无法绕开的名字。

我准备把 Greg Schmidt的程序KCube1.0分析一下，希望真正
对2-phase理解。

大名鼎鼎的CubeTwister里有一个求解的程序，大家在网上下载到源码以后，
在这个目录层次下可以找到：
cubetwister-2.0alpha125src\CubeTwister\src\main\ch\randelshofer\rubik\solver

这个程序是把KCube用Java重写了，喜欢看java代码的朋友可以看看。

遇到难的地方，大家一定要不吝赐教啊。

有人支持吗？

感谢大家的支持

夜雨听风
329774632
AlphaCB
mengfl
斜月

yanzi7816
今夜微凉
zbyxzh
dangerxxxx
r_517

yq_118
臭虫
ynyht
superflip
oyyq99999
superacid
铯_猪哥恐鸣
ggglgq
cube_master

[ 本帖最后由 aubell 于 2010-5-1 15:52 编辑 ]

aubell

先占领沙发，如果有十个以上的支持者，那么就地分析。
十位齐了，开工了。

这一楼准备分析一下概况，顺便介绍些入门知识给初学的朋友，高手不要笑话啊。


原始文件概况：
一共23个文件，10个头文件(.h)，10个C++文件(.cpp)，
一个KCube.exe,一个readme.txt,一个批处理文件(.bat)。

头文件和C++文件基本一一对应，不对应的有：
kocimovt，只有头文件；kcube只有cpp文件。

运行后，将增加几个文件：
6个.mtb文件，5个ptb文件。
这几个是查表用的文件，在第一次运行的时候生成，以后每次运行直接调入内存，
就连CubeExplorer也是这样工作的。生成的表总共占硬盘空间：6M多。
这个数据远小于CubeExplorer4.64生成的64M表。所以在计算时可能不会达到极速。
CubeExplorer4.64在使用优化的时候，要用637M的硬盘表，1G内存。

所以，写这种程序，要先估计一下空间。
全部状态都存储下来，是不可能的。

最牛的程序，个人认为是Tomas Sirgedas在一次竞赛中写的程序，没有使用外部表，
而速度很快，步数也很少，基本上解都在33步左右。那个程序很短小，但越是短小
的程序，通常越难分析；何况那个是为了比赛“最短小的程序”而写的，代码长度
优化后，可读性势必要打折扣。

所以，选择分析这个很长的、而且作者作了注解的程序。

结论：时间和空间是要考虑的因素；不是越短的程序越好读懂。

编译器：这个代码之在VC6.0下可以编译通过。
有很多地方不符合现在的C++标准。
莫非这个代码是标准出来以前就有的？

所有源代码，包括空白行和纯粹注释行，3117行。
有注释总共913行，纯注释的行412行。
所以代码不算长。但初学的朋友看到了会觉的很长。
其实写到后来，会发现，最关键的只有几行而已。
我会把不那么重要的部分先分析了，这个算是LittleEndian吧。

为什么统计的时候把空白行也算上呢？
因为程序中的空白行是为可读性服务的。假如密密麻麻不留白，会很难读的。
所以建议初学写程序的朋友注意留白、注释。

1.第一个文件 SAMPLE.BAT
给出了一行命令
kcube U:WWRYOOGBY D:BWROROYYR F:WGORWBOGG B:WRORBBWOR L:YWOYYGBBG R:BGGRGYBWY
从这个命令行能看出什么呢？ U D F B L R，显然是六个面，
每个面以后跟9个字母，BOY一类都有，RGB也有，w是白的，那么就是颜色；可每个面九个
贴纸按照怎样的顺序输入呢？
大概作者会说明的，多半在README中吧？

2.README.TXT
打开来瞧瞧，介绍了作者Greg Schmidt为什么要写这个程序，也是为了
深入理解Kociemba的算法，同我们的目的一样，在 Mike Reid 的建议
下开始写的。最后还有他的联系方式。
还列出了完整的文件包括哪些，防止残缺。
中间有一句“Please see cubemain.cpp for instructions on how to
invoke this program”,让我们到cubemain.cpp中找如何用这个程序。
但给出的文件没有cubemain.cpp，大约疏忽了，那就猜哪个是主调文件吧。
找同kcube.exe同名的cpp就是了，因为写程序，难免会疏忽，何况写帮助。

3.kcube.cpp
果然是主调程序，main函数就在这里面。命令行程序通常只有一个入口，
通常都是main。
这里的注释给了个展开图：
//For example, consider the following "unfolded"
// cube:
//              Red Red Wht
//              Yel Wht Wht
//              Wht Red Red
//
// Wht Wht Grn  Org Yel Yel  Blu Red Org  Yel Grn Grn
// Red Org Org  Yel Yel Yel  Blu Red Org  Blu Grn Blu
// Yel Wht Grn  Org Wht Org  Yel Blu Blu  Red Grn Red
//
//              Blu Org Blu
//              Grn Blu Grn
//              Wht Org Grn
//
// With the faces above corresponding to:
//
//      Up
// Left Front Right Back
//      Down
//
// Then one possible way to enter this configuration is:
//
// >cube L:WWGROOYWG R:BROBROYBB U:RRWYWWWRR D:BOBGBGWOG
// F:OYYYYYOWO B:YGGBGBRGR
这个图很重要，有了这个图，就知道输入的顺序了，是展开图的顺序。
而且，不标准的配色应该也可以。
但真的在输入的时候，也不会很轻松，搞反前后左右的事情很常见，弄错弄丢一
两片贴纸也很常见，这是命令行程序的缺点；就算用图形界面的CubeExplorer，
有时都会输入错误。而且，等它给出答案，你还要在魔方是试试，看对不对... ...
真佩服早期玩电脑的朋友，在DOS下，内存没多大，界面没图形，
那时的解魔方的程序是怎样写的呢？怎样玩的呢？
魔方难，程序难，魔方程序就更难了。
魔方好玩，程序好玩，魔方程序就更好玩了。
言归正传。
main函数里出现了四个类的对象，

FaceletCube faceletCube;
CubeParser cubeParser;
KociembaCube cube;
Solver solver;

名称起的好，让我们顾名思义，整个流程是这样的：
parser接受命令行输入的，并且为facletCube着色，
facletCube检查一下，着色是否正确，如果着色错误，直接退出；
正确的话，就转化成一个Kociembacube，让solver来解。

[ 本帖最后由 aubell 于 2010-4-15 20:02 编辑 ]

aubell

4.所有的头文件
头文件给出了类的定义，先看每个类公开了那些属性、方法
总共10个头文件，Vector和combinat两个文件没有定义类，其余都定义了类

CubeParse接受键盘输入，着色FaceletCube；FaceletCube接受着色输入，检查输入；在检查输入的时候，会顺便填写一个Cube的状态码；KocimbaCube则可详细分析Cube的状态，分别来设定各种状态。以上类在4个头文件。

表的管理，有两种表，MoveTable和PruningTable，MoveTable有六个子类，都在Kocimvot中定义，这个文件没有对应的cpp;MoveTable声明是一个独立的文件；PruningTable是乘法表（或分支表？），感谢铯告知，是剪枝表，这个是专业的称呼了。 存储内容可视作深度值。所以有3个头文件是管理表的。

Solver不必多说，最硬的骨头大概在里面。

值得注意的是类的继承，基类中的函数有虚有实。




[ 本帖最后由 aubell 于 2010-4-15 21:17 编辑 ]

aubell

5. VECTOR 和 combinat
这两个是作者的最基本的“库”

vector是向量，这里就是简单的整数数组而已。vector.cpp中定义了两个
函数，CopyVector和PrintVector，前者简单的调用库函数memcpy完成数组
拷贝，后者就是依次输出数组内容。这两个函数没有什么特别的地方。但
这个类定义了Vector，意味着比数组高一点的抽象。

combinat，组合
名称虽然叫组合，但combiant.cpp中，不仅定义了组合，还定义了排列。

NChooseM函数：计算选择数，就是通常用二项式定理或者杨辉三角计算的选择数，
实现的比较美观和高效，值得学习。作者在注释这个函数时，对排列组合的介绍十分详细。
详细的过了，呵呵。只要注意第一个参数大，第二个小就行了。

OrdinalToPermutation和PermutationToOrdinal函数：
因为魔方会用向量来表示，也就是一个数组。数组顺序就表示了魔方不同的方块在不同的
位置，假如 [01234567] 表示的是原始的魔方八个角的位置， [10234567]就表示特定的两块换了
位置。这是两个不同的排列。有人说了：你直接用整数10234567表示角块的排列不就得了？何必还
要弄个数组呢？其实直接用整数也未尝不可，但在转动的时候操作不同的位不是那么方便和直观。
所以这里有排列和整数之间的转换，当然不是直接连起来就得了。这个算法是经典的算法。
使得固定长度的全排列同连续的整数一一对应，相互转换。

也就是说，一个整数对应着唯一种排列，一个排列只有唯一的这个整数同它对应。
这个经典的算法，假如让我们自己设计，大概只有天才才能设计的出。
作者说了，他也是从书上照搬的。
因为经典，计算机专业的同学都会学习到，生成排列和生成组合的方法。
由于不是专业的，就只尝试一下结果看看，不详细分析来历。
试了一下4的全排列，没看出什么规律来，就发现0123是最后一个。
0:3 0 1 2
1:3 1 0 2
2:3 2 0 1
3:3 2 1 0
4:3 0 2 1
5:3 1 2 0
6:2 3 1 0
7:2 3 0 1
8:1 3 0 2
9:0 3 1 2
10:1 3 2 0
11:0 3 2 1
12:2 0 3 1
13:2 1 3 0
14:1 2 3 0
15:0 2 3 1
16:1 0 3 2
17:0 1 3 2
18:2 0 1 3
19:2 1 0 3
20:1 2 0 3
21:0 2 1 3
22:1 0 2 3
23:0 1 2 3
这个算法给出的顺序和CubeExplorer帮助文件中给出的似乎不同。
不是严格的降序或升序。
但这没有关系，只要一一对应就好。

其实，许多朋友都想直接拿一个整数代替整个魔方的状态，
那个整数可能很长，操作起来也不会方便到哪儿去。如果配合好的hash存储，
也是有可能的。

这个程序的做法是：把排列对应的整数存储到表中，记录下在某个操作下
会到达哪一个新的排列对应的整数。

(

补充
所以，从魔方排列到整数的工作只做一次，以后每次搜索，
都直接使用硬盘上存好的状态转移表(move table)。
状态转移表的索引方式是这样的：
新状态=Table[旧状态][操作]

)

为什么这里只提到位置排列，不理会方向呢？
（ 方向也是使用类似的movetable ）

因为2-phase是受到Thistlethwaite方法启发而设计的。虽然是基于复杂的群论的方法，
但表现在魔方是很自然和简明的方法，

原始的Thistlethwaite分四步走：
(1)还原所有棱的方向
（这个“方向”的表现形式同盲拧四步法是一致的）
   可以使用18种基本操作(RUFBLD，加'的,加2的)
(2)还原所有角的方向，同时，让E层的棱回到E层
   可以使用14种基本操作(FB两个面90度的旋转被禁止，要转就转180度)
(3)调整角和棱进入到适当的位置
   可以使用10种基本操作(RL两个面90度的旋转也被禁止)
(4)还原魔方
   可以使用6种基本操作(UD两个面90度的旋转也被禁止)

2-phase把(1)(2)两步合并了，(3)(4)两步合并了。
也就是说，2-phase的第一步是还原了所有块的方向，并且额外做了一项工作：
E层的棱回到了E层；所以在第二步还原整个魔方的时候，就不再考虑方向了。
巧妙的是，由于对某些操作“禁止”了，在第二个步骤，无论怎么转动，都不
会破坏第一步的工作成果。这正是我们所期望的。

由于不同的程序“禁止”的顺序不同，第一步“色、面优先级”的表现形式会有不同。
有的时候，有了限制反而有了自由。呵呵。

小结：这两个文件给出了与排列组合有关的计算方法。
最重要的是让排列方式同整数一一对应。

[ 本帖最后由 aubell 于 2010-4-16 23:45 编辑 ]

aubell

第五层也要，好了，不占楼了。

如果支持者有10位以上，就开始分析了。

感谢大家的支持

夜雨听风
329774632
AlphaCB
mengfl
斜月

yanzi7816
今夜微凉
zbyxzh
dangerxxxx
r_517

臭虫
superflip
superacid
铯_猪哥恐鸣
ggglgq
cube_master



-----------------------------
6.faceletcube
这个类的定义在facecube.cpp中，名称容易引起误会。
let-表示小，facelet是指一个一个的小色块。
我就干脆称其为贴纸了。这个是贴纸水平的魔方。
表现在程序中就是：用户输入一个一个的颜色，程序给魔方贴贴纸。
在有GUI的程序中，就表现为着色了。

一旦用户着色完毕，我们要还原魔方了。没有见过机器人还原魔方的
朋友总是会问：“我把装错了的魔方给机器人，不知道会怎样”。人
们总是好奇的，期望着看笑话。所以，我们程序的第一步，肯定是：
检查着色正确与否，然后还要检查组装正确与否，不然的话，瞎转半天，
不能还原都不知道。

如果不希望做这些步骤，那么可以一开始就用一个完整的魔方，让用户
输入打乱，而不是贴纸颜色；问题是，想还原一个已经打乱的魔方，又
不知道打乱公式，那怎么玩？鸡生蛋，蛋生鸡... ...

检查参数是为了保证数据的完整性。
这个贴纸层的魔方公开的方法有：
着色、检查、输出错误信息、输出魔方的状态、面的名称变为数字。

着色的方法提供给parser用，parser从命令行接受到数据，解开，着色。
输出错误信息、输出魔方状态是很自然要做的。

面的名称变成数字，是这样的顺序 UDLRFB-012345

这个类中，重点是检查，比较精彩的代码也在这里，检查的内容包括：
中心、贴纸、角、棱、角和棱一起。

中心看是否有六个，每个要唯一，不能重复；
贴纸看是否每种颜色都是9片；
角看旋转方向加起来是否被3整除，不整除就是错的；
棱看翻转方向加起来是否被2整除，不整除也是错的；
检查方向其实是很繁琐的事情，这部分工作要格外细致。
角和棱一起，就看是否组装成只有两角交换没有棱陪伴的情况--孤立Parity。

代码中，检查Parity的一段最精彩。没有读过这段代码的朋友，可以试想一下：
你会怎样检查呢？
代码中的方法很朴实，但很有效。一般还想不到，很难想到。
我以前的程序，检查的时候竟然先编了一个盲拧的编码，然后看编码是否正确。冤。
作者的用这个方法很好，值得我们学习。
看过以后，就知道是怎么实现的。隐约知道是正确的。但为什么正确，就讲不清楚了。
请何方高人讲透彻一些？为什么排列中，元素向后两两比较的结果可以用来计算是否有Parity?
关键段落：
// Permutation parity can be computed by counting the number of
//   reversals in the permutation sequence, - i.e., the number
//   of pairs (p,q) such that p>q and p precedes q.  Then
//   determine if the result is even or odd.  Do this for both
//   edges (EPP) and corners (CPP). A configuration is reachable
//   if EPP=CPP.  (August/September cube.lovers - Vanderschel/Saxe)
int FaceletCube:: PermutationParity(int* permutations, int numberOfCubies)
{
int p, q;
int permutationParity = 0;
for (p = 0; p < numberOfCubies-1; p++)
{
  for (q = p+1; q < numberOfCubies; q++)
  {
   if (permutations[p] > permutations[q])
    permutationParity++;
  }
}
return permutationParity%2;
}


棱和角都有Parity或者都没有parity，就是正确的。

出现孤立Parity是组装错误。

facecube.h中有一宏值得推荐
#define FacesToCorner(face1, face2, face3) (((face1*6)+face2)*6+face3)
#define FacesToEdge(face1, face2) (face1*6+face2)

这个是传说中的秦九韶记法，很花俏的。

（下转31楼）

[ 本帖最后由 aubell 于 2010-4-19 12:53 编辑 ]

夜雨听风

支持，虽然我看不懂，为大众服务

宇枫 幽蓝

还没学C++，对程序不了解，但也支持LZ，以后可以学习下！

AlphaCB

我愿意出10分之1的力

mengfl

这样的事是一定要顶的。。

斜月

我来十楼，哈哈，支持支持～