It's quite weird how wandering/walking is such a common way to open your mind. I also found that when going abroad I would be filled with creativity. Maybe being removed from my home habits and games. Or maybe because the foreign context stimulates your brain. Somehow it seems like physically changing your perceptions triggers opportunity for your brain to change its view on abstract things too.
So much of your thinking and habits are tied to your immediate environment. For example, people find it much easier to overcome addiction when they move to a new location where all the triggers for their addictive behaviour are removed.
Problem solving is similar in that your current environment constrains your thinking. Getting up and changing your environment changes the constraints on your thought processes. The bigger the change in environment, the more constraints removed and the greater the opportunity for creativity.
A nice twist about environment constraint is mere people presence. My last mission I was shifted one hour later than the usual schedule. At 6pm the office emptied, and as soon as I was alone, felt like my mind expanded against the walls. Freedom and motivation rushed, I could bubble in my ideas without thinking of anything or anybody else.