Ah, fair enough, there must have been some simpler ones there as well. It just was not the kind of thing I would have hacked on for fun :-)
I was thinking more of all the cool search problems like Strawberry Fields, Traversing the T or Palindromic Pangram, where coming up with some solution is easy, a naive exhaustive search for the optimal solution was not feasible, and where verifying the validity of any heuristics / pruning was not necessarily trivial.
