要说编码 首先要说到我们采用展开图的方式 让使用者输入一个魔术方块的状态 但是因为考量到要让旋转的action较为容易 编码并没有直接用每一个面9格的状态 而是采用立体小方格的编码方式 先将整个方块转成27个立体小方块 扣除掉看不到的中心方块 以及六个不会改变状态的每面中心方块 所以用20个小方块来代表一个大方块的状态 也因为当每一个小方块的朝向确立时 这个小方块所能在大方块的位置是唯一的 所以就不需要描述小方块在大方块的相对位置了 定出如何表现一个魔术方块的方法後 接着要开始描述sat式子 首先要描述的部份 分成 initial state final state action action exclusion frame 几个部份 首先定义一个步数steps 把state加上第几个时间点编码产生一组变数 每个state包括20个(如果2*2的魔方就只有8个)小方块*24个朝向 initial state 就是时间0 第一步旋转後就是 时间1 ........... 第n步就是时间 n 而final state就是时间 (steps值) action 要描述在precodition下会动到的方块状态 我们采用corner和edge的小方块分开的表示法 所以把coner的编码和action独立出来 就自然变成 2*2的魔方实作了 采用的方式 举个例 (a,4,0) 且 u_0 -> not(a,4,1) 且 (a,1,1) 最前面那个括号中的a表某一个颜色组成的小方块 4表示他的朝向(也暗示了他的位置) 0 表示他的state u_0表示第0时间点选择采用了上层顺时针旋转 描述完action的rule後 要加上 一个时间点只能有一个action发生 以及至少有一个action发生 的action exclusion条件 但是这样还有一个重要的问题 就是要描述在一个action发生时 所有不变的小方块规则 否则将会造成 选定上层旋转了 但下层却自动乱转等错误发生 这就是frame的问题 我们采取用 "一个state的变化必定是哪些action的影响" 这样式子的写法 上面那句话的逆否命题 就可以确保 如果没有发生会影响到小方块的旋转法 小方块的状态将不会变化 最後将所有条件取交集就可以送入solver解了 接下来要分析输出档 如果是satisfiable 要撷取出旋转法的变数部份 然後解码输出旋转法 如果是unsat 就要继续递增steps 然後回到前面 重新产生sat式子……如此回圈下去 而这样就可以解出当一个方块是确实可解的问题了 但还要去解决若一个方块是无法转出正确的情形的判断法 这个部分就比较数学了 大致上就是下面这个link中的东西 http://members.tripod.com/~dogschool/rubikscube.html 我们用五个规则去检查 前两个是在编码过程 1.若是读到不符合的颜色号码 2.若是产生不可能存在的方块，例如是不相邻的颜色出现在同一个小方块 3.用odd permutation和 even permutation去检查 corner 和 edge cubelets 4.同样用上述方法去检查 facelet of corner 和 edge(事实上只须查 edge的) 5.用twist的parity 去检查所有的corner cubelets 如果有任何一个规则不合正常的方块 就是UNSOLVABLE 这就将所有的unsolvable给涵盖完了 我刚看了一下你写的东西 还差蛮多的… 我已经觉得极度不妙了~~~~ 唉~~ 你明天不是还要考试吗？ 这样包括书面、投影片和有剩下code的实作 真的很多未完成 我这两天应该已经想出该怎麽具体去 完成unsolvable的判断法 但还没coding ………… 总不会要我全都做吧… magulo~~~~ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 220.135.58.37