魔方打乱程序思路

woyujnss

这个原本是只准备发在我博客上的一篇文章，不过我还是觉得这个还是应该让更多的人看到吧，所以也发到吧里来了。点击这里查看原文
如果本贴有发错区的话，麻烦版主辛苦一下帮忙移动，谢谢。

之前在网上下载了一个魔方打乱程序手机版（WM平台），程序中的打乱可以说是糟透了，RLR’这样的出现很多，但最让人郁闷的不是RLR’，而是居然还让我见到了DD’这样的公式，真是有够开玩笑的，所以想到了写这篇文章，我不是专业的程序员，也就不写什么例程之类的了，只写写我想到的方法。
首先我把魔方打乱公式中的转动方法分为18种，按照U、U2、U’、D、D2、D’、F、F2、F’、B、B2、B’、R、R2、R’、L、L2、L’这样的顺序来把这18个转动方式编号为1-18（顺序一写要是正对的两个面是连在一起的），再准备三个整数变量I1、I2和I3。
然后在出打乱公式第一步的时候生成一个1到18之间的随机数并把这个随机数保存到I2中。
接下来出打乱公式的第二步，生成随机数（一样是1到18之间的，后面没特别说明的就是1到18之间的），并把第二步生成的这个随机数保存到I1中，这时要做一次检查，以防止出现UU’或者RR2这样的公式出现，这里我的检查方法很简单，直接检查(I1-1)/3的整数部分是否等于(I2-1)/3的整数部分，例如第一步是U，第二步是U’，那么现在I2的值是1，I1的值是3，放进我前面说的两个公式里就是(3-1)/3=0.666…和(1-1) /3=0，它们的整数部分相等，检查结果就证明了第二步如果是我刚才的例子则是废步，那么就重新生成一个随机数并保存到I1中去吧（条件循环）；再举个例子，第一步是R2，第二步是L’，对照我的18个编号可以看到R2是14，L是18，那么两个公式就是(18-1)/3=5.666…和(14-1) /3=4.333…，此时两个结果的整数部分不相等，这个情况下就说明R2L’不是废步。
接下来就说说第三步吧，第三步开始时先把I2的值保存到I3中去，然后I1的值保存到I2中去，比如刚才前面所说的I2是14，I1是18，那么经过我现在所写的之后，就应该变为I3=14，I2=18了，然后再次生成随机数，并把这个新的随机数保存到I1里，进行一次刚才第二步时一样的检查，也就是看 (I1-1)/3和(I2-1)/3的整数部分，这里就不废话了，接下来检查第三步会不会造成和第一步产生废步，也就是说不可以有RLR或者F2BF’这样的公式出现，检查方法也很简单，先看(I1-1)/6和(I2-1)/6的整数部分是否相等，如果不相等则第三步没有和第一步产生废步，后面的步骤可以跳过了（原理很简单，稍微想想就知道了）；但是如果先看(I1-1)/6和(I2-1)/6的整数部分相等的话，那么就还要再检查一次了，这次要检查的是 (I1-1)/3和(I3-1)/3的整数部分，如果相等则说明产生废步了，不等则不是废步。就拿刚才的第一步是14(R2)，第二步是(L’)来说吧，第三步如果是L、L2和L’这三个的其中之一，那么在第一次检查（除以3的）时就不通过了（请自己将18个编号套用公式算一下，后面都不写出公式的计算过程了）；那么第三步如果是R、R2和R’这三个其中之一的话，那么第三步第一次检查则通过，于是进入第三步的第二次检查（除以6的），这里由于前面一步是属于L转的三个状态之一，所以要进入第三步的第三次检查（也是除以3的，不过I2换成了I3）了，这时就会发现第三步和第一步出现废步，重新生成随机数给 I1吧（条件循环）。
现在生成第四步，再往后面和第四步是一样的，就不用写了。首先是把I3里保存的数字输出成文字，也就是I3为1则输出U，为2则输出U2等，，接下来就是完全和第三步一样了，没什么好写的了，
然后是就最后一步了，当生成到了最后一步时，检查完了I1不是废步就直接把I2和I1里保存的数字输出成文字，至此整个没有明显废步打乱公式就生成成功了，我想写的也写完了，呵呵。
PS：对于18种转动在大部分编程语言里应该是可以写成一个文本数组吧？

最后附上我用上面所说的方法生成的100步公式吧，看看上面写的方法是否正确的。

B’F2R D R2B L’F L2B2L2U’D2L’F2B2D’L B R2B2U B’U2D’B'R2B L2U F’B2L’R B2D’U L D L’B L’R2U R2B2F2U’D2R’L2F L’B2D2B L B2F U B2D F B2L2F2L2D R’F'L2D L’D L2D’R2F2B2R F’D F B D R2L’B2L2B2F’U'F2L2U D R’U'F2

[ 本帖最后由 woyujnss 于 2011-6-9 21:57 编辑 ]

aubell

楼主在这里也贴个附件吧？没有天堂的帐号，不能下载。

aubell

很强啊！excel都能写出如此漂亮的程序。
我阅读过的其它程序的源码是这样做的：
一个随机数（1，2，3，4，5，6）生成要转动的面，一个随机数（1，2，3）生成要转动的角度。
程序只要保证
（1）当前的“面”跟前一个“面”不同；
（2）如果前一个面是相对的面，当前的面不能跟更前一个相同；
（3）相对的面只能以固定的次序出现，如打乱公式中只能有LR，就不可以有RL。

楼主的方法很有启发意义，值得学习。

楼主见过的产生“废步”的打乱，大概是写程序的人太懒了才导致的，
要不就是没有玩过魔方的程序员写的，要不就是不拘小节造成的... ...但不可鄙视他们啊。

因为真正一点“废步”也没有的打乱程序是很难写的，因为只要长度大于20步，一定可以被化简；
长度小于20步的，也有可能可以被化简。淡定看待每一个打乱程序，只要不是太离谱都可以了。

[ 本帖最后由 aubell 于 2011-3-10 19:28 编辑 ]

woyujnss

原帖由 dkjiaoyang 于 2010-7-6 16:53 发表


看明白了……开始还想不通上上一步的……看明白了

也许应该叫做“再上一步”之类的吧，不好意思，中文水平不太好……

die4live

5楼的上传来看看啊 链接的论坛没注册

dkjiaoyang

原帖由 woyujnss 于 2010-7-6 14:52 发表
简单点来说原理就是看上一步是否与本步转的是同一个面，是的话就肯定是废步。然后看上一步是否与本步转的是不是对面，如果是的话就再检查上上步是否与本步转动为同一个面，是的话就也是废步。
举例子的话应该就是上 ...

看明白了……开始还想不通上上一步的……看明白了

gb57

http://www.cube-china.com.cn/bbs/viewthread.php?tid=6176&highlight=%B4%F2%C2%D2

我以前用excel写过一个打乱程序玩

woyujnss

简单点来说原理就是看上一步是否与本步转的是同一个面，是的话就肯定是废步。然后看上一步是否与本步转的是不是对面，如果是的话就再检查上上步是否与本步转动为同一个面，是的话就也是废步。
举例子的话应该就是上一步是R的话，本步为R、R2和R'这三个之一就为废步，也就是我写的(I1-1/3)和(I2-1/3)取整数部分来判断；上一步是R，上上步是L的话，本步为R、R2、R'、L、L2和L'这六个之一则是废步，后面的除以3和除以6就是做这样的检查。

[ 本帖最后由 woyujnss 于 2010-7-6 14:55 编辑 ]

dkjiaoyang

C语言考了62 ~~
多步的检查还看不懂

专业新手

高人来讨论
七年级看不太懂