c - 启发式移位数组

给定目标状态

int final[3][3]={{1,2,3},
                 {4,5,6},
                 {7,8,9}};

作为一个随机的初始状态,我只想通过移动表的行(右或左)和列(上下)来将数组排序为final
   7 8 4    by shifting to the right the first row it will become 4 7 8
   2 1 9                                                          2 1 9
   6 5 3                                                          6 5 3

所以我想用一个*搜索,我试图找到一个好的启发。
我已经试过使用错误放置的数组元素。
有什么建议吗?


最佳答案:

我认为这是一个代数问题。给出了一组由6个循环(3行3列)生成的置换,您希望找到更多的移动来帮助您获得任何置换。
第一条建议:不是所有的排列都是可能的!由于每个移位都是偶数置换(3个周期是两个置换的组合),所以只有偶数置换是可能的。因此,您将无法找到任何配置的解决方案,其中除了(2,1,3),(4,5,6),(7,8,9)中的两个交换数字之外,所有配置都已就位。
第二条建议。如果r是行移位,c是列移位,则计算rcr'c'的作用,其中r'和c'是逆移位。这个“换向器”又是一个由3个元素组成的循环,但这次它们不在一行或一列中。通过选择不同的r和c,可以得到很多3个循环,这可以在第三条建议中使用。
第三条建议。考虑已经处于最终位置的数字区域。对这个集合的补集应用3个循环来减少它,直到得到一个解决方案。

译文:来源   文章分类: c a-star heuristics

相关文章:

c - 线程中的动态分配和释放

c - 将字体从文件加载到Pango?

c - 正确使用getopt

c - 按位记忆

c - c入门手册加上第6章ex12

c - 如何为Zynq 7000 ARM开发板编写SPI驱动程序?

c - 打印字符串给出字节C [重复]

c - scanf验证用户输入

c - 为什么不能同时使用静态和寄存器存储类?

c - 什么是多重编译,如何工作,为什么我应该使用它?