I know that I learned the basics of chaining things together to get an effect by experimenting on my own in QBasic; basic graphics and audio were super easy, so I could also experiment with the difference between internal data state and how to represent that state.

When I started a directed education, learning new programming concepts always expanded the set of problems that I could solve. Learning how to reason through them didn't come separately, it came through writing programs of increasing complexity over time.

Before learning any meaningful amount of programming, I was introduced to the idea of examining the capabilities of your available tools and using them to find creative solutions...with adventure games.

I would consider a curiosity for exploration and experimentation to be central requirements to become a problem solver (at least through the path that I did). Start with that general mindset, present a world for them to explore, introduce them to the tools they can do it with, and there's no way to stop them from that point on.