不到 800 行代码，彻底搞定魔方还原问题

VC 可以编译运行，或者用 mingw 的 gcc 编译都可以

msys2 + mingw32 环境下编译方法：
gcc -Wall -o cube cube.c

总共代码不到 800 行，还原速度在 10s 左右，当然还可以进一步优化。


一些符号的含义：
F - 正面，程序运行后白色的这一面
B - 背面，黄色面
L - 左面，紫色面（标准魔方应该是橙色，但是 windows 控制台无法显示橙色，用紫色替代）
R - 右面，红色面
U - 上面，蓝色面
D - 下面，绿色面


命令说明：

魔方操作命令：
f  - 正面顺时针旋转
f2 - 正面 180 度旋转
f' - 正面逆时针旋转

其他面以此类推：
f2 f' b b2 b' u u2 u' d d2 d' l l2 l' r r2 r'

init  - 魔方复位
rand  - 随机打乱魔方，可以直接 rand 或者 rand n，n 为随机打乱次数
input - 输入魔方状态，按照提示输入即可
solve - 自动还原魔方
help  - 帮助信息
exit  - 退出程序

所有命令都是用小写字母。



数据结构和算法说明：

数据结构方面，每个面都用简单的二维数组来表示。要点是六个面的旋转操作的实现，以及魔方状态的显示，和状态输入。

算法方面，主要是用到了启发式的广度优先搜索。要点在于魔方状态的评估函数，剪枝方法，搜索算法等。

当然，你还得懂魔方。

程序代码量不大，也写得足够精简，可仔细品味。如有不懂可以提问。



搜索算法说明：

程序将魔方状态分为以下阶段（每个阶段完全归位会加 4 分）：
fcross0  - 正面十字还原，不包含第一层的边块
fcross1  - 正面十字还原，包含第一层的四个边块
fcorners - 第一层全部归位
medges   - 一二层全部归位
bcross   - 一二层全部归位，并且第三层做出十字
bsurface - 底面做出十字
bcorners - 第三层角块归位
bedges   - 第三层边块归位（彻底还原）

在进行搜索时，按以上的顺序，分阶段的完成搜索。
cube_check_state 是魔方状态的评估函数：
当参数 flag 为 0 时，是从 fcross0 开始评估 cube 能到达的最好的还原阶段
当参数 flag 为大于 0 的数值时，实际上是指定了一个目标阶段，评估函数会从 fcross0 开始评估，直到达到这个目标阶段最多能得到多少分（也就是有多少方块归位）

flag 等于 0 时，主要用于计算当前的 cube 状态，是否达到了目标状态
flag 大于 0 时，用于计算在给定的目标状态下，当前 cube 能得多少分，主要用于剪枝操作。
比如说，我都已经两层还原了，如果当前扩展出来的节点，跟两层还原相比差太远了，我就没必要保留这个扩展节点了。

search 函数是一个广度优先搜索的算法实现，采用了 open 表 + close 表来扩展节点并进行搜索。
open 表做为一个队列来使用因此是广度优先。close 通常用来检查某个节点是否已经被扩展过，实测如果加上这个检查，反而速度变得非常慢，因此 close 表没有真正用到。