I agree it's hard to build a simple solution to a complex problem, but not necessarily wrt what we normally talk about as problem solving skills in programming.
What I mean is the hard part is stepping back and actually solving the real problem in the best way. That might be utterly trivial code wise, it might be brute force vs optimal. It might be just solving a readily parallelisable problem on a single thread. It might be a unilanguage monolith instead of microservices in the 'right language for every task', etc.
The smartness involved in making code simple (and I mean simple, not elegant) is more about pragmatism, lateral thinking, discipline and focus on end goals than any sort of analytical smartness.
(Making simple code for complex problems is hard!)