Manhattan Distances, but Linear Interference...

Question

Manhattan Distance does not take into account linear conflicts. For example:

- - 3,1 needs to be changed to - 1, -, 3

[Only first row is being shown here, and the blank is assumed to be at the top left corner.]

Manhattan Distance is 4, but tiles 1 and 3 interfere with each other while moving.

So, how can we improve this heuristic?

Answer 1

For every liner conflict, it will take at least 2 more moves, like choose one of them to move down and up. We can add 2 for heuristic as some kinds of penalty.

There seems to be a lot of good solutions to this problem.

http://idm-lab.org/bib/abstracts/papers/aaai07b.pdf