Since there are two slightly different questions here
one in the topic
What student exercises force them to modify and extend their own thinking process and methods?
and one in the detail section
In the context of extending their thinking and problem solving skills, what particular problems and exercises would you suggest to use at the novice level for teaching computer science?
I am going to give an answer about exercises that focus on problem solving skills. The odd thing when I was building this list is how much it reminded me of those aptitude test they give you in grade school.
When it comes to problem solving one first has to be aware that there is no one way to solving problems that always works and there may not always be an answer to a problem or there may be an answer but getting the answer is not practical.
Algorithms commonly used
Depth First Search
Breath First Search
Divide and Conquer
Inferencing - Analogy: Connecting the dots
and also thinking in orthogonality of dimension/field.
For one of the simplest exercises of using depth first search is the game Unium which is to simply draw a line connecting a set of selected squares. This basically has only one dimension, a line and one method, depth first search. The puzzles get harder and harder, but you basically start drawing the line, see a problem, back up to where the problem occurred and then choose a different option and keep going and repeating until you complete the object and onto the next image to cover. This teaches that for some problems you can go back to a decision and change it to get the correct solution.
For breath first search the game checkers works as you can't make your next move until your opponent has made theirs and so can't resort to DFS. OK I know it really is a min-max game but BFS still applies. This teaches one that you have to look at all options available before moving.
For divide and conquer you will needs something that has simple rules and allows you to move off a sub-problem if it is to hard but still allows you to solve the problem. For this MineSweeper is a good game. This teaches that if you get stuck on something hard try some place else and you can still get the answer; in other words some paths to the solution are easier than others.
For something a little harder try A Good Snowman Is Hard To Build as this requires at least one good a-ha moments to build a snowman. The rules are simple but is uses three dimensions. When I did this with my small class it seemed most of the students had the same a-ha when building a certain snow man because the way to the solution seemed illogical, but until one learned to do the illogical they were stuck. I won't say what lead to the a-ha moment but I suspect that if you play the game you too will be saying a-ha at one point.
So far the way of thinking has been procedural but to add some functional thinking take a look at the Great Permutator as this adds functions, e.g. partition using every other, accumulate, dup, swap among others. I like this one also because you can try out different combinations of the function parts before solving the whole problem.
For a game that adds the dimension of concurrency take a look at SpaceChem. While this doesn't look like programming if you know how to program with locks and fork-join you will see the patterns and the best part is that it is visual. If my teacher had used this when teaching OS design it would have been a lot easier.
Getting back to procedural and adding in variables and the Jump instruction take a look at Human Resource Machine. One of the better parts of this is that it has challenges for the least number of steps and the least number of instructions. The answers to these challenges are not intuitive but get you to realize that machines don't have to work like we think to get a better solution.
For more advanced procedural/functional and back to the essence of what a microprocessor/ALU does check out Silicon Zeroes. This one also covers the idea of parameters and state.
To get out of the algorithm type problems have fun with the Crazy Machine Elements collection. This will make you think and sometimes you can even find solutions that don't use all of the parts. What is nice about these problems is that some of the elements affect others in nonintuitive ways like reversing gravity. This teaches that you can't always have orthogonality of dimension.
When you start playing with the dimension of time things really get interesting but finding a game that is simple but alters just time is not so easy to find, but The Misadventures of P.B. Winterbottom seems to do the trick. This game reminds me of a single person composing a song by recording a melody, playing the melody back and adding on another melody and so on. Get one melody wrong and you have to start over. This is interesting in that it teaches one that time is also a critical dimension for solving some problems.
Speaking of playing with different concepts what about having cooperating concepts? That brings us to Portal and Portal 2. I only wish they took the idea of cooperating concepts further and used other fields such as time, color, etc, and also have them competing some how. This is really interesting because it bring lots of a-ha moments if you don't look for the answers online.
The Turing Test changes out different dimensions/fields for solving the problems in different rooms but makes them harder as you go so that you are continuously being challenged. This helps to teach you that different properties of certain things can be used for other than their primary use, e.g. a block has weight but it can also block a beam.
For more of a real world problem but still simple enough for learning an essential concept common with neural networks being classification would be Papers Please. I have not yet played this one, but if it doesn't live up to what other say I will strike it from the answer.
Another game I have yet to check out but seems to deal with graphs which are essential to so many data structures in computer science is Mini Metro.
For the concept of composition I have on my list Infinifactory; again one I have not personally vetted.
So as you can see to learn how to problem solve start with simple methods and limited dimensions and keep adding on slowly with fun using games and one can learn a lot about problems solving.
In the real world when there are known to be exact solutions to a problem I tend to find that brining in combinatorics helps to solve the problem and one puzzle that quickly jumps to mind here is a Rubik's Cube. If you know the basic moves and how to apply them you can even find God's Number which will teach you a lot of good math and computer programming algorithms.
For more look at puzzle and logic problem books as they have lots of exercises. I did one of these books decades ago using Prolog before it had constraint satisfaction and after seeing how constraint satisfaction worked with Prolog find it to be one of my favorite languages for problem solving when dealing with closed world assumptions.
So by now for problem solving with computers you can see the need for algorithms (methods) and data structures (dimensions/fields) which is why the book Introduction to Algorithms is so popular.
If you have reached this far then check out the book "How to Solve It" by G. Polya. While it is useful to both students and teacher, it is limited in that it was written with math in mind.
If you are learning programming and reading this, I can not stress enough how much you should learn other paradigms of programming, e.g. procedural, functional, logic, and other concepts like matrices in MatLab, neural networks and learn as much math as you can.
One last point that AFAIK seem to be the only one I know who uses this rule when faced with a problem I can't solve. Most advise is to back off, break the problem apart and tackle a simpler part. However at times I find that finding a harder problem and reading about it then makes my problem easier and more enjoyable. So go regularly read about quantum mechanics and theoretical physics, etc., and you hopefully you will see that your problem is not that hard.
I can spend much more time on this question but hopefully I have given you enough to get started and shown you the path to expanding on how to build out ones problem solving toolbox.
