查看: 238036|回复: 10

编了一个计算魔方的程序 [复制链接]

guxl

蓝魔

Rank: 2

积分: 244
帖子: 2
精华: 0
UID: 13
性别: 男

电梯直达

1^#

发表于 2004-3-13 08:47:07 |只看该作者 |正序浏览

编了一个计算魔方的程序

可以手工求解，将魔方拆散拼装，计算机搜索，自动求解。

系统需求：如果用计算机搜索功能，需128M以上内存，其它功能对计算机要求较低，相信目前大部分计算机都能满足。操作系统：在WIN98上测试通过，其它未测试。

★可以用程序中的“随机转动”的功能将魔方打乱，然后手工还原。
★可以将魔方拆散拼装，根据网上查找到的资料，如果任意地组装魔方，只有1/12的机会可以再通过转动来还原它。我想到一个简单的办法，可以立即排除5/6的无法还原的状态，但余下还有1/2的可能无法通过转动来还原。我的大致结论如下：仅考虑八个角上的角积木，仅有1/3可以还原；仅考虑十二条棱上的棱积木，仅有1/2可以还原，这两方面程序都可以判断出来，余下的是角和棱无法同时还原的，还没想出什么准则来排除。
★程序提供了自动搜索的功能，几经改进算法，目前可以做到在赛扬800计算机上在数分钟内计算10~14次旋转的魔方还原，如果内存>192M，可以计算12~14次旋转（同一方向的转动属一次，每多一次转动可能状态就多15倍）。大约相当于遍历了10的14次方种状态。不过由于魔方的状态太多，色彩组合理论上有2^12 * 3^8 /12 ~= 4.32 * 10^19 种，离能求解所有类型的魔方相差还太远。看来用程序搜索解法的方法还必须想想其它方法。
★程序提供了用口诀自动求解的功能，道理上可以求解所有可以通过转动来还原的魔方。如果有无法还原的，可能是因为：1、确实就无法还原，2、程序中有BUG。

使用方法：
拆散拼装,按“拼装”按钮，显示出两个魔方，上面的魔方是已还原的，点击要移动的小积木，在下面的图上点击要移动到的新位置。上图中用阴影表示已有新位置的小积木，下图中用灰色表示尚空缺的位置。
按“求解”按钮搜索还原步骤，按“Option”设计搜索选项。
按“用口诀求解”按钮用口诀自动求解。
求解的转动步骤用“查看结果”依次显示，或用“<<”“>>”单步显示。

程序中记录移动的方法，根据网上通常的表示方法，说明如下。魔方上有六个面，分别用首字母表示：
上面　Upper, or top face = U
下面　Down, or bottom face = D
左面　Left face = L
右面　Right face = R
前面　Front face = F
后面　Back face = B
旋转时，以右手转动该面来确定是顺时针还是逆时针。
旋转的方向表示如下:
逆时针旋转90度用该面的代表字母表示，如U表示上面逆时针旋转90度，U1表示同样的意思。
顺时针旋转90度（等同于顺时针旋转270度）用在该面的代表字母后加撇号或加3表示，如U'或U3表示上面顺时针旋转90度。
旋转180度用在该面的代表字母后加2表示，如U2表示上面旋转180度。

参考了 http://rubik.yeah.net ，感谢rubik提供了这么多资料。

谁要程序，我发给他。

收藏0