Completely free backbone design is a *very* hard problem, as there are just too many degrees of freedom. There’s no way to efficiently sample all of them. Instead, people usually take a few simple approaches in flexible backbone designs to limit the complexity.
The first is to do multiple rounds of packing and minimization. You design the structure, minimize the sidechains and backbone to the new structure, then do another round of design, minimize to the new design, etc. (Usually for ~3 rounds or so.) This is the approach typically used in Rosetta enzyme design and a large portion of the protein-protein interaction design.
The second is to actively perturb the backbone (e.g. with backrub or with loop remodeling) to generate a library of different starting backbone conformations, and design for each one (optionally with multiple pack-min cycles). You would then run a filter (using whatever metrics you want) on the results to eliminate those starting backbone conformations which give bad results.
If you have a certain interaction that you *really* want, you can try placing the interaction and then rebuilding the loop containing it to accommodate the placed amino acid position, e.g. by using cyclic coordinate descent (CCD) or kinematic closure (KIC). (This last approach is sometimes referred to a “hotspot”, “stub”, or “motif” approach.)
.
