If a problem is NP complete, it is unlikely you are ever going to try all possible solutions (at least for large values of N). Instead your only option is to improve the probability that a correct answer will fall within the first X solutions tried. In that respect, order matters a great deal.

Best, beth