The cube from rockcarry

不到 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 表没有真正用到。

rockcarry / cube Goto Github PK

cube's Introduction

cube's People

Contributors

Stargazers

Watchers

Forkers

cube's Issues

请问oplisttab是怎么得到的？

算法询问

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent