Ultimately problem solving is the application of varying knowledge sets to a unique scenario. If we've encountered the scenario beforeor one very close to itand know how to solve it then we're no longer really problem solving but rather applying a method or equation to a new set of data. Teaching basic algorithm's to accomplish particular tasks (like sorting a list) is a matter of understanding concepts and learning to recognize the scenario that requires it's use. This too, falls short of true problem solving. Only when a problem involves factors or combinations of factors that we haven't encountered before are we truly solving a problem.
Problem solving is not an easy skill to teach. If we were to teach someone to swing a bat or do a dance move the learner's neurons would "mirror" ours as we demonstrated it so that they were learning it just by watching. However, problem solving is largely a skill of the mind. It's difficult to demonstrate our internal process to a student.
Problem solving comes down to a series of questions we can ask ourselves to guide us through the process. Luckily this process has been studied and turned into a methodology in George Polya's book How to Solve It.
This post is meant to help instructors teach their students to solve problems.
Essential Teaching Methods
The immediate instinct of many teachers when a student is struggling with a problem is to come in and either solve it for them or explain to them how to solve it. The Problem with this approach is that the student only learns how to solve that problem rather than process of solving problems in general.
For this reason we need to explore a method for teaching that should help us teach the process as well as the information.
The Socratic Method
Rather than simply lecturing or stating information to his followers, Socrates would teach by asking a series of questions. The questions were designed to cause the hearer to think about what was being said and consider any objections or disagreements logically (read: critical thinking). This lead them down their own personal path of discovery by assisting them through the process.The method is successful because it requires a student to essentially teach themselves with the assistance of a mentor. When a student is required to answer questions they become more mentally engaged and develop a deeper comprehension of the subject matter.
That's not to say that giving information has no place. In fact, one of the main benefits of using the Socratic Method is that is allows you as the teacher to understand the missing pieces in your students knowledge or abilities. If you ask enough questions to them they will eventually either solve the problem or you will come to a point where they need your direct instruction to accomplish something. Either way you've accomplished something with that student.
A Brief Description of Polya's Process
Mathematician George Polya came up with a four step process for solving problems.

Understanding the Problem. No problem can be solved without first being understand. This goes beyond merely recognizing a pattern that has a predetermined algorithm to solve. The person must understand the fundamental underpinning of the problem, otherwise they are following a memorized procedure rather than really understanding what they are doing. If they understand what they are doing they can apply what they know or even alter it to fit a new condition. Before a problem can be solved the student must understand what the problem really is.

Breaking down the problem into steps or pieces. Ultimately all problems are just an amalgam of smaller problems. Once we've broken it down into smaller pieces we can begin to evaluate what steps we know how to do and which ones we don't. In this way we can begin to a) apply current knowledge, and b) know what knowledge we need to learn or discover.

Execute plan. Follow the steps given. The most important part of this is to learn to check our steps. If we code our solution and then test it as a whole it becomes difficult to debug if incorrect. It's important to check each step and ensure that we're getting the results we intend. Then we're debugging in pieces rather than everything.

Look back. Looking back on a solved problem can be extremely beneficial because it helps us make connections and potentially create abstractions. Can pieces of this code be abstracted to assist in solving other problems? Is there code already written that we can use our solution instead of writing new lines of code? Can we make our code more readable or coherent? Can we simplify our solution? What patterns or algorithm's did we use to solve this problem? What new tools/concepts/facts did we learn to solve this problem and how can they be used elsewhere? What did we learn when debugging our solution? Asking pivotal questions will help students glean concepts that can be reused in the future.
Application
So now to put it together. How do we use the Socratic method with Polya's method? Simply ask questions that take the student through this process.Probe for Understanding
The first question should be to simply ask them to describe the problem. Make them give details, ask followup questions, and ensure true understanding of the problem. Ask them to tell you what information we *do* know, and what we don't yet know but might be useful in solving it. Defining the "knowns" and "unknowns" of a problem will help them immediately begin to see steps that need to be taken. If they can't explain it to you then they don't understand it.Breaking it Down
After that we need to get the student to break down the problem and create a plan of action. If they've defined what is unknown then you might begin by asking them how we might discover that information.Ask them to begin by writing pseudocode of the steps that need to be taken. Ask them how they solve each step. If a step is particularly complicated have them break it down into it's own smaller steps. Refrain from doing anything to help them except ask questions. Break the problem down into smaller and smaller pieces until they can either 1) solve it's pieces or 2) need some information to solve the pieces. It may be teaching a concept like inheritance or a builtin element of the language.
Executing with Checking
As they begin to execute their plan, if you see an error, again, rather than just pointing it out, ask them questions that may help them realize what they are doing wrong. For example, ask them what they are expecting will happen on the step they are on. Ask them what a particular key word or method does in general. By asking them this you can help them think about what they doing more deeply. Ideally you continue to ask questions until they see their mistake. But it will also help you understand the fundamental misconception, misunderstanding or lack of knowledge they have.By addressing the root of their error you can correct it long term.
Correcting them immediately is hacking at the branches of the issue; it's just going to crop up again and again. Rather, we need to get down to the true lack of understanding so that we can fortify their knowledge and correct misconceptions.