How does one teach problem solving? In teaching university level Computer Science, I find many students struggling because they lack basic problem solving skills. Having them do more practice problems does not help as they get stuck at those or somehow hack together a solution to some problems but cannot generalize to other problems. Walking them through some solutions does not help as they might understand that solution but are again unable to transfer that to another problem.

I thought math competence would ensure logical thinking and hence problem solving but I have seen enough counterexamples by now.

The conclusion I seem to be getting to is one that I do not like: problem solving is an innate skill - it cannot be taught.

How have others dealt with this problem?
I speak from experience teaching (and doing) mathematics, and supervising research students for some decades. First, as with nearly anything, of course there can be some degree of innate interest+capacity...

What I have observed is that ... seemingly inevitably... academic environments inadvertently train most students to worry as much about conformity to the teacher's expectations as they do about the subject itself. This tends to cause critical thinking to wither, and the whole thing spirals downward.

Also, by this point it is really not clear to me that mathematical competence is strongly related to logical thinking, and, further, I don't think problem-solving facility is much related to logical thinking (of the highly linearized sort that mathematics is often caricaturized into). If anything, the standard mathematics style seems to me to not only squelch the kind of experimental, no-rules thinking that (genuine/serious) problem-solving requires, but to strongly disavow that experimentation is a legitimate methodology.

And, indeed, in many contexts, exams and such are structured with time limitations so that experimentation is infeasible. Other traits can be rewarded in timed exams, but not experimentation, and, I think, therefore, not problem-solving (unless of a fairly stylized sort).

To draw students into a better problem-solving attitude I think requires more iteration than most courses have time for. That is, a substantially dialected/Socratic process, in which weak solutions' weaknesses are illustrated by just-slightly-hard problems that thwart the weak approach. Repeat and repeat. But this takes a lot of time, since the psychological processing of such meta-issues is not "logical", but something subtler, from what I have seen. Changing one's viewpoint apparently cannot happen overnight.