Comment by theGnuMe

Survey Propagation is one of the best algorithms for solving very hard SAT instances.

Here's a good review paper that captures it.

http://www.cs.cornell.edu/~sabhar/publications/surveyPropUAI...