The paper describes a constraint-based solution to the protein folding problem on face-centered cubic lattices - a biologically meaningful approximation of the general protein folding problem. The paper improves the results presented in [15] and introduces new ideas for improving efficiency: (i) proper reorganization of the constraint structure; (ii) development of novel, both general and problem-specific, heuristics; (iii) exploitation of parallelism. Globally, we obtain a speed up in the order of 60 w.r.t. [15]. We show how these results can be employed to solve the folding problem for large proteins containing subsequences whose conformation is already known. C