A* Admissible Heuristic for die rolling on grid

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

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)