更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19526480

大意

最小的步数达到要求的地方。

思路

这个题目的目标状态也很简约，就是形如题目中的样子，这个我们转换思路就是拿着这个空格去和旁边的格子不断的交换，但是这样产生的状态是很多的，为了剪枝，我们采用 IDA*，这个题目的估价函数有个很显然的写法，就是记录错误位置的个数，因此，一定小于等于...吗？我们考虑这样的情况，如果现在只需要一步，将空格和一个棋子交换，这样的实际步数是 $1$，但是你的估价函数给的是 $2$，显然不行，特判一下即可。然后我们就正常的去迭代加深的搜索就好。