我一直在研究滑动瓷砖拼图的通用版本，其中瓷砖没有数字。相反，每个位置都有一个瓦片或一个洞，并用布尔值表示为真或假（瓦片或洞）。
搜索的重点是采用具有 n 个瓦片的初始状态和具有 n 个目标位置的目标状态，并使用 A* 找到如何移动瓦片以使每个目标位置都被填充的解决方案。下面是一个 4x3 网格的示例：
Initial State:
T F T F
F F T F
F F T T
Goal State
T T T T
T F F F
F F F F
我一直在研究不同的启发式方法来做到这一点，最成功的一个逻辑是这样的：
int heuristicVal = 0
for every tile (i)...
int closest = infinity
for every goal location (j)...
if (manhattan distance of ij < closest) closest = manhattan distance of ij
end for
heuristicVal += closest
end for
return heuristicVal
不幸的是，在启发式方法将两个或多个图块引导到同一目标位置的情况下，这仍然太慢了。我尝试乘以heuristicVal瓷砖的数量，突然间出现了指数级的加速。之前需要 28 秒的问题需要不到 1 秒。
编辑：事实证明，这种变化并不总是产生最佳解决方案。但是，我不明白为什么它的速度如此之快，或者为什么尽管不再被接受，但它仍然找到正确的（尽管不是最佳的）答案。