&gt; <i>&quot;you&#x27;re stuck with checking all N! solutions&quot;</i><p>not quite -- once you have a solution that runs in time X, you no longer need to check any solution that has a sub-component that is known to take longer than time X.  So, for example, if you find that going between locations A, C, J, F, P, E, and Q in that order takes longer than your current best whole-map solution, then you no longer have to check any solution of which ACJFPEQ is a subset.  You can eliminate whole categories of solutions with a single check, instead of having to test each of them one-by-one.