I would however argue that if you can tell the difference between a good and a bad solution of the problem (through some utility function, or fitness function f

I would however argue that if you can tell the difference between a good and a bad solution of the problem (through some utility function, or fitness function for evolutionary algorithms) you do have some understanding of the problem. But, yes, I agree that you could just arrive at the correct solution through random chance. I guess a better description is that to solve a problem we either need an understanding of the problem or enough resources and time to exhaust the solution space.