面试题
设计一个魔方的数据结构,并给出从不规则状态到规则状态的路径搜索算法
个人感觉好难!
[解决办法]
n块的魔方,麻烦一点,难道是没有多难。
不考虑时空复杂度的算法:
状态搜索算法,定义好状态空间,定义好转换动作,定义一个判定函数
就可以了。
一个面9块的魔方,一共有27个小方块,其中
1个没有面暴露(体中心方块,忽略)
6个有一个面暴露(面中心方块)
12个有2个面暴露(棱方块)
8个有3个面暴露(顶点方块)
只要把这些个方块的位置表示出来,状态空间就定义好了
转换动作:
从魔方的玩法可以知道,每一次可以旋6个面中的任意一个,规定一次旋90度。可以定义只能顺时针旋,或者都可以旋。
这样,转换动作就定义好了
判定函数简单略