我正在开发一个程序来解决这个臭名昭著的难题。我使用 A* 搜索和曼哈顿距离启发式的原始方法非常适用于 4x4（15 拼图）的棋盘，并且可以非常快速地解决它们。我调整了我的算法以适应大于 4x4 的板，首先尝试解决外部行/列，直到它变成一个 4x4 板，然后可以用通用 A* 算法解决。这似乎只适用于最大 5x5 的电路板，因为当电路板变得大于 5x5 时，使用 A* 算法和经过调整的启发式算法首先解决外边缘问题，这从我的尝试来看是不可行的。所以我开始寻找其他解决外边缘的方法并找到了本文中使用的方法：https://arxiv.org/pdf/1610.04964.pdf 问题是，我真的不确定如何将此伪代码转换为实际代码。我通过将各个图块移动到正确的位置来理解它所呈现的想法，但我不确定如何高效而简洁地实现这一点。如果有人能阐明或推动我朝着正确的方向前进，我将不胜感激。
我认为保留获胜板索引的哈希图以及当前板的索引以用于即时查找 moveCell() 函数将是有益的。我还跟踪空单元格的 x/y 坐标，因此无需不断搜索索引。