It's noteworthy that you are describing one of the many ways to do a heuristic search. It doesn't mean that the general form of a problem is not NP-hard, just that a good enough solution can be approximated or an optimal search can be made tractable, by adding more information.

This angle was very prominent during the first AI "revolution" wherein casting AI as search problems augmented by human knowledge was in vogue.