寻找魔方程序

echo

我记得以前在一本杂志上看到过解魔方的程序,好象是一次比赛的题目.可惜没能找到程序.不知道这里的爱好者有没有.

cube_master

摘自：http://www.cbe21.com/subject/maths/html/040601/2002_11/20021128_2015.html

魔方解法的一点想法

一、概念 面(face) -- 魔方有6个面，分别标为(u,v,w,x,y,z)，其中(u,v,w)分别是 (x,y,z)的反方向。 状态(status) -- 魔方的所有可能的不同色块排列。一般的表示为S。 初始状态(S[0]) -- 魔方6面各自同色的状态。 动作(action) -- 迎着每一个面有左转90度(left)，转180度(opsite)，右转90度(right)等3种操作，共18种基本动作。分别标为： (ul, uo, ur, vl, vo, vr, wl, wo, wr, xl, xo, xr, yl, yo, yr, zl, zo, zr) 先执行动作A，再执行动作B，称为复合动作，简称动作。记为：A*B 二、算法 一个状态集S，为每个元素配一个深度指标。 1、 加入初始状态S[0]，深度为0。 2、 S中每个新加入的元素，执行18个基本动作。 3、 对每个动作的结果，如果不在S之中，则加入S之中，深度为被操作对象的深度加1。 4、 反复执行2到3，直到S不再增长为止。 对于魔方的一个状态S，查找上述状态表得到深度d。执行18个基本动作， 一定至少有一个动作的结果深度为d-1，确认该动作为一步。反复尝试和确认，一 定能够到达初始状态S[0]。 状态集S中元素个数的估计：六个面的中心点不因动作而变化，8个顶点与12 个棱，应当有 8!*12! 约50M个状态。虽然顶点和棱在位置上还有自由度，但是顶点和棱之间也有相互的约束关系。我不能定量地计算各自的程度，但是我觉得PC机的计算能力应当可以对付，至少值得一试。 三、置换与等价 置换 -- 魔方的空间摆放方式有24种。每种方式对应唯一一种面之间的置换。由于(u,v,w)总是(x,y,z)的反方向，所以只要确定(x,y,z)的置换即可。以某一面着地时第一象限的三个轴标记为： (yzx, zvx, vwx, wyx, // u面着地 zxy, xwy, wuy, uzy, // v面着地 xyz, yuz, uvz, vxz, // w面着地 zyu, ywu, wvu, vzu, // x面着地 xzv, zuv, uwv, wxv, // y面着地 yxw, xvw, vuw, uyw) // z面着地 所有置换构成置换群。其中L[xyz]为1元。 状态的等价关系 -- 对于魔方的两个状态S与T，如果存在一个置换L，使得 S*L = T 则称S与T等价。 动作的相似关系 -- 对于魔方的两个动作A与B，如果存在一个置换L，使得 S[0]*A = S[0]*L*B 则称A与B相似。 四、算法的优化 一个状态集S，为每个元素配一个深度指标。 1、 加入初始状态S[0]，深度为0。 2、 对S中每个新加入的元素，执行18个基本动作。 3、 对每个动作的结果，如果不与S中任何元素等价，则加入S之中，深度为被操作对象的深度加1。 4、 反复执行2到3，直到S不再增长为止。 对于魔方的一个状态S，查找上述状态表中与之等价的状态，得到深度d执行18个基本动作，一定至少有一个动作的结果，其等价状态的深度为d-1，确认该动作为一步。反复尝试和确认，一定能够到达初始状态S[0]。 引入置换和等价关系，实际上是以时间换空间。因为这个算法的主要问题是空间开销太大，所以这种平衡是值得的。 五、算法的实现 我还没有真正动手做，仅仅提供一点建议吧。 1、 可以用0,1,2,3,4,5表示6种颜色。6个32位整数表示一个状态。每个整数表示一个面。整数中每三位表示一个色块。 2、 用32位整数表示深度应当足够了。 3、 调试时可以先选择三个基本动作，通过后再选择六个基本动作，这样一步步扩大。 六、其他 各种智能算法的评价函数可不可以用对状态表的统计分析的方法得到？

rongduo

读了Cube_Master所摘的:关于计算机魔方还原程序的构想，现仅就我自认为已读懂的某此部分发表浅见，供参考。

第一， 关于魔方的状态数或组合数。引文给出的估算数为：

12!*8!≈1.9×10¹³

从其思路来看，似乎考虑的只是方块位置的组合，而未考虑方向组合。但即使如此，这一算法可能仍然存在着问题。我的计算结果是：

12!*8!/2

魔方组合数的计算极为复杂，这里无法细谈，我只想给出我最终的计算结果：

12!*8!*2¹¹*3⁷/2≈4.3*10¹⁹

这一数字是依据我的跷跷板原理算出来的，它与我以前见到的某些可信的结果完全一致。毫无疑问，这是一个极大的数字。如此的量级，PC机是否可以在一个合理的时间内完成任意一种组合的计算，我是有疑虑的。

今天暂说到这儿。

cube_master

rongduo 朋友：当你下载 cube319 用一下，你的顾虑很快就会消除了。

rongduo

读了Cube_Master所摘的:关于计算机魔方还原程序的构想，现仅就我自认为已读懂的某此部分发表浅见，供参考。

第一， 关于魔方的状态数或组合数。引文给出的估算数为：

12!*8!≈1.9×10¹³

从其思路来看，似乎考虑的只是方块位置的组合，而未考虑方向组合。但即使如此，这一算法可能仍然存在着问题。我的计算结果是：

12!*8!/2

魔方组合数的计算极为复杂，这里无法细谈，我只想给出我最终的计算结果：

12!*8!*2¹¹*3⁷/2≈4.3*10¹⁹

这一数字是依据我的跷跷板原理算出来的，它与我以前见到的某些可信的结果完全一致。毫无疑问，这是一个极大的数字。如此的量级，PC机是否可以在一个合理的时间内完成任意一种组合的计算，我是有疑虑的。

今天暂说到这儿。

rongduo

第二，关于魔方状态的描述。引文把任一状态记为S（i），且所说极为简略，我怀疑是否可行。

用定性的跷跷板原理去解释魔方，原本用不了很多数学，但为了使这一原理有一个可靠的理论背景，我仍然尝试进行了理论的思考，现将思考结果略述如下。

1．必须完全确定魔方前后左右上下六个平面，确定每一个方块的本位向，然后引入方块的状态函数S（p,d）（有时我把它叫作位能），p表示位置，d表示方向。

2．当方块处于本位且方向正确时，其位能等于零。否则p,d二者至少有一个不等于零，此时位能亦不等于零。

3．为了确定地、唯一地描述方块的位置和方向，须要对代数中的二元数（描述角块位置）和四元数（描述边块位置）的算术略加改造，使之适合于我们的目的。

4．有了二元数、四元数的工具，一个方块的状态可以这样描述：它有本位向、当前位向和当前位能三个参数；仅当知道其中的两个参数时，方可推断第三个。

以上所说仍有耍花架子的嫌疑。但在一个帖子中又只能如此，言不及义，不妥处还望网友海涵。

cube_master

rongduo 朋友：当你下载 cube319（下载） 用一下，你的顾虑很快就会消除了。

5188

恭喜rongduo前辈荣升魔方贵宾！！！[em17][em17][em17]