Transform it. It's sometimes possible to transform a hard problem in one domain to an easier problem in another domain. This is similar to, but different from, going meta. Going meta is exactly what it says on the box, involving an increase in abstraction, but no change in domain, so that the problem looks the same, but with more generic features. Transforming a problem doesn't necessarily change its abstraction level, but does change the domain so that the problem looks completely different.

My favorite example comes from the field of lossless data compression. Such algorithms try to find patterns in input data, and represent them with as few bits of output data as possible. (Lossy data compression algorithms, like MP3 and JPEG, discard data that humans aren't expected to notice. Discarding is the most effective compression method of all, but lossless algorithms can't get away with that.)

One way to design a lossless data compression algorithm is to directly attack the problem, building up a list of patterns, which you can refer back to as you notice them occurring again. This is called dictionary coding, and you're already familiar with it from the many implementations (like ZIP and gzip) of the Lempel-Ziv algorithm and its many derivatives. LZ is fast, but it's old (dating from 1977-1978) and doesn't compress very well.

There are other approaches. As of several years ago, the most powerful lossless data compression algorithm was Prediction by Partial Matching, developed in 1984 according to Wikipedia. PPM uses Fancy Math to predict future symbols (i.e. bytes) based on past symbols. It compresses data really well, but is rather slow (this is why it hasn't taken over the world). The algorithm is different, but the approach is the same, directly attacking the problem of pattern matching.

In 1994, a new algorithm was developed. Michael Burrows and David Wheeler discovered something very interesting: if you take a string of symbols (i.e. bytes), put every rotation of it in a matrix, and sort the rows of that matrix lexicographically (all of this might sound hard, but it's easy for a competent programmer to write, although doing so efficiently takes some work), then this matrix has a very special property. Every column is a permutation of the input string (trivial to see), the first column is the symbols of the input string in sorted order (also trivial to see), and the last column, although jumbled up, can be untangled into the original input string with only 4 bytes (or 8 bytes) of extra data. The fact that this transformation can be undone is what makes it useful (there are lots of ways to irreversibly jumble strings). (Going back to the overall point, transforming a problem isn't useful until you can transform the solution back.)

After undergoing this (reversible) Burrows-Wheeler Transformation (BWT), your data looks totally different. It's easier to see than to explain. Here's some text that you might have seen before:

Three~Rings~for~the~Elven-kings~under~the~sky,#Seven~for~the~Dwarf-lords~in~the
ir~halls~of~stone,#Nine~for~Mortal~Men~doomed~to~die,#One~for~the~Dark~Lord~on~
his~dark~throne#In~the~Land~of~Mordor~where~the~Shadows~lie.#One~Ring~to~rule~t
hem~all,~One~Ring~to~find~them,#One~Ring~to~bring~them~all~and~in~the~darkness~
bind~them#In~the~Land~of~Mordor~where~the~Shadows~lie.#$

And here it is after undergoing the BWT:

.me,,.,,#emeylnfee~~~##~~~~~~~##~##~~~~#~~$eeeeeklffr,eeeeeemmlsoseonoeensrndss
sddsdoefrrrnneenrnddegkgdggsrrhht~~h~LLwDdd~~nnnrnne~~n~~rraarnniiihhhhhnnnehhh
nnhrrlmrhhhhhvMvdhhnSrooo~~~~~nnnnnnSS~ttttttttttttttww~Ttdll~~bfNrRRRRkehrr-rs
lalu~~aaa-lEeeeeoeeeoIIiiaaaiiuooOOOiOkiiiiiitttt~~~o~rtdffffddLMMlMddoioooeooo
oooeehabaaaho~sigdwwlg~e~r~~~~~~~~~~~~~~~~~~~sr~leD~~ook

If you follow how the BWT is performed, what it does is bring symbols with similar "contexts" together. While sorting that big matrix, all of the rows beginning with "ings" will be sorted together, and most of these rows will end with "R" (each row is a rotation of the input text, so it "wraps around"). The BWT consumes text that is full of rich patterns (i.e. context) in the original domain (here, English) and emits text that has repetitive characters, but with no other structure.

It's hard to identify patterns (i.e. compress) in input text! It's easier to deal with repetitive characters. Solving the problem of compression is easier in the Burrows-Wheeler domain.

If you throw another transformation at the data (the Move-To-Front transformation, which is also reversible), then these repetitive but different characters (eeeoeeeoIIiiaaaiiuoo, etc.) become numbers that are mostly 0, some 1, few 2, and a scattering of higher numbers. (Everything is bytes, but I'm trying to keep it simple for non-programmers). It's really really easy to compress data that looks like this. So easy, in fact, that one of the oldest algorithms ever developed is up to the job. (Not Euclid's, though.) The Huffman algorithm, developed in 1952, efficiently compresses this kind of data. Arithmetic coding, which is newer, is optimal for this kind of data. Anyways, after applying the BWT, everything afterwards is much easier.

(I've glossed over Zero-Length Encoding, which is a transformation that can be applied after MTF but before Huffman-or-arithmetic that further increases compression quality. It's yet another example of how you can transform yourself out of an inconvenient domain, though.)

(Note: I haven't kept up with recent developments in lossless data compression. 7-Zip is powered by LZMA, which as the acronym suggests is Lempel-Ziv based but with special sauce (which resembles PPM as far as I can tell). However, as it was developed in 1998, I believe that the history above is a reasonably applicable example.)

(Edit: Replaced underscores with twiddles in the BWT example because apparently underscores are as good as stars in Less Wrong formatting. Second edit: Further unmangling. Less Wrong really needs pre-tags. Third edit: Trying four spaces. Random thought: My comments need changelogs.)

Great topic.

Ask someone who has been in a similar situation or solved a similar question or tried to solve a similar question. This may seem obvious, but is often ignored.

Be ready to recognize a bad answer when you see it. Sometimes, what looks like a good answer at the outset develops fatal problems. Don't vest too deeply in your answer. But don't be afraid to keep your answer just because others view it as different or scary.

For Wei Dai and everyone else here offering their own tips and tricks: what hard questions have you answered using them, and which tricks helped the most?

Expanding on the go meta point:

Solve many hard problems at once

Whatever solution you give to a hard problem should give insight or be consistent with answers given to other hard problems. This is similar in spirit to: "http://lesswrong.com/lw/1kn/two_truths_and_a_lie/" and a point made by Robin Hanson (Youtube link: the point is at 3:31) "...the first thing to do with puzzles is [to] try to resist the temptation to explain them one at a time. I think the right, disciplined way to deal puzzles is to collect a bunch of them: lay them all out on the table and find a small number of hypotheses that can explain a large number of puzzles at once."

His point as I understand was that people often narrowly focus on a limited number of health-related puzzles and that we could produce better policy if we attempted to attack many puzzles at once (consider things such as fear of death, the need to show we care, status-regulation, human social dynamics: particularly signaling loyalty).

Edit: I had originally meant to point out that solving several problems is a meta-thought about solutions to problems: i.e. they should relate to solutions to other problems

I like the last bit about status, and would add the following...

Kobayashi's Paradox #1: The more you know about one thing, the more you will be expected to know about everything. However, the more you know about one thing, the less you probably actually know about everything else.

Kobayashi's Paradox #2: Status (or your perception of your own status) is inversely proportional to the amount of productive, creative work you will actually get done. (This suggests that perceptions of status do not update as quickly as they should, or are not based upon a current assessment of the person's worth/productivity.) If you need/want to get work done, shun the distractions of 'status'.

Nice points. I'd also add;

Spend time thinking about it. It's something that seems obvious, but I know I pass over it more than I should. Since answers seem to come unconsciously it's tempting to just wait for a solution to arise and to go think about other things. Unless you keep the problem in your head during down-time, before going to bed, in the shower, taking a walk etc... then you won't be processing for an answer. It's tricky to coax subconscious thoughts to answer the questions you want, but continual conscious thought on the topic is the most straight forward approach in my experience. If you're thinking about other things, you won't get an answer.

Hoard knowledge for its own sake

Related to "explore multiple approaches" and cognitive diversity; don't let all your learning efforts be focused on a single question, for in all likelihood your hard question is going to require insights from surprising directions. Cultivate the childish pleasures of pure curiosity.

I don't work on cosmic problems in my day-to-day work, but I encounter puzzles fairly frequently (what broke? why did performance at node x decrease at time y? why does z work well sometimes but not others?).

Advice I would give:

• Get some data. If you have too much data, arbitrarily pick a subset you can handle.

• Look for anomalies. Make histograms. Make other graphs. Last weekend I diagnosed a problem with a Windows service with a graph of the Fourier transform of a time series picked out of log files.