I'll second and constraint-solving algorithms; specifically, the variable-ordering heuristics seem helpful to me. Choose the variables which most constraint the problem first! Note, the constraint propagation step is another instance of the sum-product algorithm. :)