FindShortestTour shows erratic behaviour wrt 2nd argument

Question

FindShortestTour behaves erratically. It should return a {distance, ordering} pair, and it does this for most values of its second argument. But for two cases shown below, it returns an empty list. There is no mention of this possibility in the Mathematica documentation. There is no apparent reason for this behaviour. There are no errors or messages thrown during execution.

places = {{-0.16799965940098155`, 
0.24175153562415813`}, {-0.2486071472529178`, 
0.20618977684683304`}, {-0.14076440088637684`, \
-0.24171243009574903`}, {-0.6251900796628861`, -0.9717675903858705`}, \
{-0.17963581832506564`, -0.5233794053664629`}, {0.266014045257439`, \
-0.2574537949317151`}, {0.43866600854230675`, -0.3502551214679294`}, \
{0.8152887752208928`, -0.152895668542801`}, {0.0849331507331597`, \
-0.09587917268794487`}};

Array[FindShortestTour[places,#,9]&,8]

If you copy and paste and execute this code, you will see that the 3rd and 6th entries are empty. Why?

Answer 1

I'm not sure why this happens, but you can work around it by changing the distance function from its default. For instance:

Array[FindShortestTour[places, #, 9, DistanceFunction -> ManhattanDistance] &, 8]

returns answers for all the cases. There seems to be something special about your "places", since if you choose the locations randomly, it seems to mostly work fine:

places = RandomReal[{-1, 1}, {9, 2}];
Array[FindShortestTour[places, #, 9] &, 8]