八数码难题 (IDA*解法）_对于八数码问题曼哈顿距离之和

翻题解的时候看到大佬们都打的双向广搜。（蒟蒻在墙角瑟瑟发抖

在这里提供一种IDA*解法，
还是一层层地搜索，如果超出预期层数就返回
然后用评估函数进行剪枝（就是可行性剪枝）
感觉写起来比双向广搜好多了

评估函数越好，搜索效率越高；
如果评估函数太差，那IDA*和普通爆搜复杂度差不多。
所有一个好的评估函数很关键；
主要是看这道题评估函数(h)怎么写，

对于评估函数想到的有两个方案：
方案一：不在自己应在位置上数的个数；
方案二：所有数距自己应在位置的曼哈顿距离之和；

很显然选第二个方案更优，（虽然方案一也可以AC）
因为一个数移动到自己目标位置，至少要移动它现在位置到它目标位置的曼哈顿距离

例如下面这一个

它的距原状态的曼哈顿距离和就是4（1+1+2）
（不用计算0，因为其它数字归位后，0也会回到原位）

至于如何实现，可以先开一个数组记录任意两位置之间的曼哈顿距离
然后再开一个数组记录每个数字目标状态的位置

大概是这样的

int dis[9][9]={
   
	{
   0,1,2,1,2,3,2,3,4},
	{
   1,0,1,2,1,2,3,2,3},
	{
   2,1,0,3,2,1,4,3,2},
	{
   1,2,3,0,1,2,1,2,3},
	{
   2,1,2,1,0,1,2,1,2},
	{
   3,2,1,2,1,0,3,2,1},
	{
   2,3,4,1,2,3,0,1,2},
	{
   3,2,3,2,1,2,1,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17