c - 移动数组的启发式

Question

给定一个目标状态

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

和一个随机的初始状态，我只想通过移动表的行(右或左)和列(上和下)来将我的数组排序为最终状态

   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

所以我想使用 * 搜索，我正在尝试找到一个好的启发式方法。

我已经尝试过错误放置的数组元素。

有什么建议吗？

Answer 1

我认为这是一个代数问题。给你一组由 6 个循环(3 行和 3 列)生成的排列，你想找到更多的移动来帮助你得到任何排列。

第一个建议:并非所有排列都是可能的!由于每个移位都是偶数排列(一个 3 循环是两个换位的组合)，所以只有偶数排列是可能的。因此，您不会找到任何配置的解决方案，其中所有配置都已到位，但有两个交换数字，如 (2,1,3),(4,5,6),(7,8,9)。

第二个建议。如果 r 是行移位而 c 是列移位，计算 rcr'c' 的作用，其中 r' 和 c' 是反向移位。这个“换向器”再次是 3 个元素的循环，但这次它们不在一行或一列中。通过选择不同的 r 和 c，你会得到很多可用于第三条建议的 3 周期。

第三个建议。考虑已经处于最终位置的数字区域。对这个集合的补集应用 3 个循环来减少它，直到你得到一个解决方案。