Earlier quoted context omitted.
Put the newbie gumshoes to work by tracking down simple bugs and designing simple patches to fix them. They need to be able to read other people's code to decipher and debug the coding style they are seeing before they are allowed to build any new module themselves. They need to understand other styles so they can form their own. They should be able to detect any code "smells" and reason with pros/cons why their impl…
I'm hoping there's a way to teach them problem solving BEFORE they learn to code... I feel like it should be a prerequisite to enrolling in the bootcamp. I don't remember how I learned it, but it certainly wasn't reading other people's code at my first job.
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.