Comment by emil-lp

It depends on what you mean by brute force, you can easily do 20 cities with dynamic programming, which essentially is brute force with pruning.