31321
21543
43212
15434
32121
Soit 63 (trouvé par ordinateur j'avoue), et j'ai 160 combinaisons (en éliminant les symétriques ça doit bien faire 40 possibilités tout ça). Par contre, aucune garantie d'optimalité, autrement dit j'ai utilisé des hypothèses qui peuvent être fausses, mais je trouve mon résultat en 3 min environ.
Je commence avec une ville vide, et je case des 1: toute case vide à la fin doit toucher un 1. Hypothèse: moins il y a de 1, mieux c'est (je trouve 7)
Ensuite je continue avec les solutions précédentes, et je case des 2: toute case vide à la fin doit toucher un 2. Hypothèse: moins il y a de 2, mieux c'est (je trouve 6)
Et ainsi de suite (6 pour les 3, 4 pour les 4) et je complète avec des 5 (2 cases restantes).
Par contre, aucune garantie donc qu'avec un 1 en plus, je n'aurais pas eu un 2 et un 3 en moins et un 5 en plus par exemple (pour un total au final de 64)