One response I'm surprised didn't get more votes at stackoverflow is thinking on paper. Not only does it make the fact that you're thinking visible and socially acceptable; it's a big help in focusing your thoughts. I use this all of the time for brainstorming, planning, or "rubber ducky debugging", and I find that I make a lot more progress on paper than trying to just do it in my head.
The permanent record is a secondary bonus, but sometimes I find writing in a permanent place like my bound notebook makes me hold back and do the thinking in my head again so that I can write perfectly, instead of just brain dumping as I think. When I get blocked like this, I switch to looseleaf, which I can toss if it turns out to be scribbles. More often I end up saving that too, though, in folders.
I work independently so I don't worry about what I look like working (and it is awful, usually messy hair and a pair of boxer shorts, who has time for a comb or pants?), but I definitely agree with the thinking on paper. Spending 15 minutes sketching out ideas with a pen saves me hours of dead-end code writing. That's especially true if I have to write a tricky algorithm of any type. I haven't seen one yet that couldn't be sorted out without a single line of code. I'm not talking about writing pseudocode either, I'm talking about drawing pictures of what an algorithm does (or needs to do). Boxes, squiggly lines and arrows are your friend. Or, to look at it another way, if you can't draw a picture of it, you don't know what you're doing yet. That mindset has made me much more productive (and saner).
The permanent record is a secondary bonus, but sometimes I find writing in a permanent place like my bound notebook makes me hold back and do the thinking in my head again so that I can write perfectly, instead of just brain dumping as I think. When I get blocked like this, I switch to looseleaf, which I can toss if it turns out to be scribbles. More often I end up saving that too, though, in folders.