魔方解法与状态深度分析

一、概念

面(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相似。(www.xing528.com)

四、算法的优化

一个状态集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.调试时可以先选择三个基本动作，通过后再选择六个基本动作，这样一步步扩大。

六、其他

各种智能算法的评价函数可不可以用对状态表的统计分析的方法得到?