Don't Get Stuck in a Rut

I was solving a practice TopCoder problem the other day, and was having difficulty. First the problem:

Imagine you are multiplying to positive integers A and B (A >= B) using long multiplication with no carry. For example if A = 89 and B = 76:

       8  9
x      7  6
------------
      48  54
+ 56  63
-------------
  56 111  54

The input to your program would be the array {56, 111, 54}. You have to return A, in this case 89. If there are multiple A's that satisfy the input, you have to return the one that minimizes A-B. To make sure the problem is feasable they constrain it by saying that the result of A*B < 10¹⁴.

I decided to approach the problem by noticing that the the most significant digit (MSD) of the answer was equal to the MSD of A times the MSD of B. I would try each combination of digits that makes this work, and then move on to the next digit. I also noticed that the number of digits in the answer equals the number of digits of A + number of digits of B - 1. So I tried every combination of lengths of A and B that satisfied these constraints, when picking digits. I then returned the one that worked that satisfied the tie breaking condition (i.e. smallest A that is >= B).

This passed all the examples provided, so I submitted it. Unfortunately it timed out on some of the system tests. Since this was a practice, I had access to the system test and copied it locally. I ran this test locally and let it run for a couple hours. When I came back it still hadn't finished. Given that the program has to solve the problem in less than 2 seconds, this was a wee bit too slow.

I finally gave upI looked at my code and found some obvious optimizations. This improved runtime from hours to 10's of seconds. Better, but still too slow. I worked at it a while longer, but just couldn't figure out how to improve my code enough to get it to run fast enough. So I finally gave up and read TopCoder's solution to the problem.

Their solution - just try every value from 1 to sqrt(N) for B. Set A to be N / B. Check if it satisfies the constraints. You can check 10⁷ choices for B in under 2 seconds, and their bounds guarantee that B won't be larger than that.

This solution is much easier to comprehend and code up than what I came up with. Yet, I didn't see it. I was stuck in a rut. This comes up repeatedly when trying to solve a problem, whether it is a small contrived problem like TopCoder or much larger "real-world" problems. Once you see an approach that looks like it might work, it can blind you to other approaches which might be better. This is really just another example of "Don't Want That", where what you need to stop wanting is your current approach.

How do you get out of this rut? The first thing that has to happen is that you have to notice you are in a rut and be open to the idea that other solutions may exist. Given this, how do you find these other solutions? One of my favorite ways is to present the problem I have to someone else without telling them my current approach. A fresh mind often comes up with a fresh solution. What if you don't have someone to discuss it with or, as in a competition, you can't discuss it with people? Then you have to try and clear your mind of everything you know. Start at the problem from scratch, considering every salient fact, paying particular attention to any that your previous approach ignored. Try to come up with the most off the wall things you can think of and pay attention to the reasons they don't work. If you have the luxury of time, put the problem down and don't think about it for a while.

Unfortunately, sometimes it is hard to describe a problem to a fresh person without sullying it by hinting at our own approach. And I often find that no matter how hard I try to come at a problem from a new angle, my mind just slips back into the old rut. So how do you get unstuck from a rut?