魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 1408|回复: 1

Thistlethwaite's algorithm 编程笔记 [复制链接]

Rank: 4

积分
1808
帖子
1033
精华
6
UID
17579
性别
保密

魔方理论探索者 论坛建设奖 六年元老

发表于 2015-7-8 20:14:44 |显示全部楼层
本帖最后由 aubell 于 2015-7-8 20:17 编辑

1.第一步 G0->G1 不是重点,也不是难点。把所有的棱方向摆成一致。
2.第二步 G1->G2 如果要存储所有状态,内存的需要稍微大些,不过可以接受。
         是重点,但不是难点。
3.第三步 G2->G3 内存的需要很少,但这个步骤是整个算法中最难的地方。
        放到后面解释。
4.第四步 G3->I 内存的需要比较大。假如存储所有状态,难在把棱的状态同数字
         一一对应。很多的实现要么采用两倍大小的空间来存储,要么使用hash
         技术存储。个人编程的时候,采用了两倍大小的空间。对于角的排列,如果
         理解了第三步的办法,那么这一步角排列是很容易pack的。
5.棱和角可以任意组合pack。

进入G3的充分必要条件:
1. 先看Jaap的代码:
内部实现时,角的排列次序
UFR UBL DFL DBR   DLB DRF URB ULF
注意这个次序的特点
(1)前4个是一组,我合称其位置为阳轨道;后面四个是一组,我合称其为阴轨道。
(2) 同一个轨道里的角处在面对角线上,不相邻。我称这种位置关系为小尖。
(3) 注意两个轨道对应的排列次序,UFR同DLB三个字母都不同,也就是说,
    它们处于立方体的大对角线上,我称这种位置关系为大斜。
    UBL同DRF也是大斜的位置关系。后面依次都是。
2. 三个元素的全排列
   三个元素只有六种排列方式。
   编码很容易:
  012 编码为 0< (小于号表示第二个元素小于第三个元素)
  021 编码为 0> (第一个元素原样抄写)
  102 编码为 1<
  120 编码为 1>
  201 编码为 2<
  210 编码为 2>
然后把 “<” 编码为0, “>” 编码为1,再pack成二进制数字
如 1> ,首位乘以2加上大于号对应的1,编码为3
3. 很多元素的排列
   也是用类似的方法来pack和unpack
   但是注意,用的不是二进制,也不是十进制。
   而是使用“阶乘进制”。
  1.    int permtonum(char* p){
  2.         int n=0;
  3.         for ( int a=0; a<4; a++) {
  4.                 n*=4-a;  //同二进制pack对比,类似二进制 shift left
  5.                          //但是每一次都shift不同的量
  6.                 for( int b=a; ++b<4; )
  7.                         if (p[b]<p[a]) n++; //数大于号的个数
  8.         }                                              //实际上是p[a]>p[b]
  9.         return n;
  10.         }
复制代码
4. 四个元素的全排列划分为6个种类
   四个元素的全排列可以划分为6个种类,怎样划分呢?
   every one ^ first item
   每一个元素与首元素异或,包括首元素。这样,首元素都是0了。
   然后用"数大于号个数"的方法 pack-perm,就会成为三个元素的排列了。
   用这种方法pack,非常巧妙。相同的种类类里,有着特殊的位置关系。
5. 两个轨道的相对扭转关系
   两个轨道是如何pack到一起的呢?
   看代码:
  1. case 5://tetrad choice, twist and parity
  2.   int corn[8],j,k,l,corn2[4];
  3. // 8 bits, set bit if corner belongs in second tetrad.
  4. // also separate pieces for twist/parity determination
  5. k=j=0;
  6. for(;++i<8;) //按照上面提到的固定的顺序查看所有位置
  7. if((l=pos[i+12]-12)&4){ //&4是就是 >=4 的意思了,因为小于4的元素&4都为0
  8.                         //这一句是说,“如果是阴轨角”
  9. corn[l]=k++;           //记录它出现的次序
  10. n+=1<<i;               //记录选择
  11. }else corn[j++]=l;     //如果是阳轨角,按顺序记录下它
  12. //Find permutation of second tetrad after solving first
  13. for(i=0;i<4;i++) corn2[i]=corn[4+corn[i]]; //[color=Magenta]按照阳轨角出现的次序,
  14.                  //查找阳角之家对应的大斜角出现的次序[/color],并记录
  15. //Solve one piece of second tetrad
  16. for(;--i;) corn2[i]^=corn2[0]; // every one ^ first item
  17. // encode parity/tetrad twist   // 24种变成了6种
  18. n=n*6+corn2[1]*2-2;             //pack起来,*6是把选择 shift left,
  19.                                  //为这六种情况空出存储位置
  20. if(corn2[3]<corn2[2])n++;       //最终结果是选择和扭转pack在一起
复制代码
6.不用再理会parity了吗?
  是。parity本质上是分两类讨论,这种pack方式分了六类。
包含了parity的情况还有角块围绕大斜线的扭转情况。所以不必再对parity讨论了。

7.进入G3的充分条件是什么?
  在阴阳分轨以后,用上面的方式pack,得到的结果同还原态pack的结果一致。




Enjoy cubing
Enjoy coding.
我喜欢的公式 U D F2 B2 U' D'

Rank: 1

积分
15
帖子
15
精华
0
UID
1346163
性别
保密
居住地
郑州市
兴趣爱好
结构
发表于 2017-12-21 18:51:32 |显示全部楼层
喜欢这个,收藏了

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2019-3-24 13:17

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部