自动还原魔方算法数据结构

来自：CSDN博客 作者：寸辰 链接：http://blog.csdn.net/cun_chen/article/details/50261787（点击尾部阅读原文前往）

今天看到一个有趣的问题，魔方还原问题，仔细思考了一下，关键点在于数据结构设计。 分析如下，简单设置魔方剖面图如下。

魔方的点主要分为三面相接的 角点 ，面相接的边点，面中心的基本点 基本点是固定的，魔方在变形过程中，基本点是没有办法进行改变的，图中1-1，2-2，3-3的相对位置是固定的，改变的只能是角点和边点，基于此，基本位置衡量必须基于基本点

根据基本点，设置边点编号如下图，相同编号表示为同一边块

设置角点编号如下图，相同编号表示为同一角块

根据上图不难看出，不论边块还是角块位置，只需要四面就可以确定全部边块及角块位置，因此设置最小确定点如图

此间需要确定一点，魔方不论如何变换，其角块对于基本点相对位置是对应的，不可能出点所以基本点按照正确位置排列，但具体色块颜色位置出现问题

基于此，我们设置魔方基本变换方法两种，边点变换和角点变换

角点变换不存在什么问题，但是边点变换存在基本点变换的问题，由于我们设置基本数据结构基于基本点，因此基本点不能进行变换，故

边点变换=左角变换+右角变换

根据最小确定点，可以设置数据结构为一维数组或二维数组。

根据基本变换方法，可以设置基本方法如下（不涉及基本点变换） 　Method turnRightClockwise() 　Method turnRightAnit() 　Method turnLeftClockwise() 　Method turnLeftAnit() 　Method turnTopClockwise() 　Method turnTopAnit() 　Method turnTBottomClockwise() 　Method turnTBottomAnit() 　Method turnOutsideClockwise() 　Method turnInsideClockwise()

设置扩展方法如下（涉及基本点变换，转化为基本方法） 　Method turnTransverseClockwise()中心横向顺时针 　Method turnTransverseAnit()中心横向逆时针 　Method turnLongitudinalClockwise()中心纵向顺时针 　Method turnLongitudinalAnit()中心纵向逆时针

可以设置值栈进行路径探索，接下来就是路径搜索问题，之后附上代码。

补充：

终点是可以确定的，只要保证相对位置符合，那最终位置就是确定的。

用栈来存储变换路径其实就是防止无限递归问题，如果发生变换到之前发生过的情况，则后退重新变化。

算法一 最优转发算法

　　百度百科里边有，已经证明了，不论在什么情况下，魔方20步之内可以还原，但由于要保证相对位置，所以中心点不可以改变，涉及到中心点的变动可以转换为两边转动，所以直接设置栈深50，这样进行完全遍历时间复杂度还是太高，所以需要根据一些基本魔方原理进行时间效率优化

算法二

　　可以采用魔方公式进行模拟，层旋发，桥式这些都是相对简单的转法，你可以自己看看

免责声明：本文系网络转载。版权归原作者所有。如涉及版权，请联系删除！