Well, I’ll add my comment here, since it is more optimal than the current highest-voted answer by @larsmans – but, I am convinced there must be something better (hence the bounty).
If I multiply the heuristic with a constant, it’s no longer admissible
The best I can come up with is (manhattenDistance/3)*6 + (manhattenDistance%3)
, where /
is integer division and %
is mod. This works because in any 3 moves with no back-tracking, all three digits will be unique, so the lowest sum we could have is 1+2+3 = 6 (The %3 simply adds any extra, non-multiple-of-three moves).
[Edit] As @GrantS pointed out in the comments above, my heuristic can be improved very slightly by adding an additional 1
when manhattenDistance%3 == 2
. This is easy to do without a conditional: (manhattenDistance/3)*6 + (manhattenDistance%3)*3/2