Thanks for the tip. I was wondering about my heuristic. I know that Heuristic algorithms need to give an answer that is below the actual path length, but I forgot that there will be occasions in this Kata where the actual cost is zero!

Following your tip I removed the heuristic, and also needed to do a little optimisation of my "find the lowest cost" search. It's still overkill, but at least it's working.

your hueristic is not good enough.
the total cost between two points on a grid is not the manhatten distance, but the total differences between each two nodes on the path.

btw, a* is overkill for this kata, if you don't believe me try having getHeuristic always return 0 ;)

Hmm. I have an A* solution that is nice and quick, and passes the vast majority of tests, but occasionally fails to produce the right answer, and when it fails the given answer is always 2 higher than the correct answer!

I've been going crazy trying to work out what the common factor is on the failed tests. Why would it always be 2 out?!