高中趣味数学(魔方解法的想法)

一、概念

面(face)--魔方有6个面，分别标为(u,v,w,x,y,z)，其中(u,v,w)分别是(x,y,z)的反方向。

状态(status)--魔方的所有可能的不同色块排列，一般的表示为S[i]。

初始状态(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[i]，查找上述状态表得到深度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[i]，查找上述状态表中与之等价的状态，得到深度d执行18个基本动作，一定至少有一个动作的结果，其等价状态的深度为d-1，确认该动作为一步。反复尝试和确认，一定能够到达初始状态S[0]。

引入置换和等价关系，实际上是以时间换空间。因为这个算法的主要问题是空间开销太大，所以这种平衡是值得的。

五、算法的实现

我还没有真正动手做，仅仅提供一点建议吧。

1、 可以用0,1,2,3,4,5表示6种颜色。6个32位整数表示一个状态。每个整数表示一个面。整数中每三位表示一个色块。

2、 用32位整数表示深度应当足够了。

3、 调试时可以先选择三个基本动作，通过后再选择六个基本动作，这样一步步扩大。

相关推荐：

高中趣味数学：被墨水盖住的算式

高中趣味数学：趣味数学三道作业题