Ο Ταξιδιώτης Πωλητής και το Δίλημμα των Διαδρομών

Ο Henry Ernest Dudeney συγκαταλέγεται στους σημαντικότερους δημιουργούς γρίφων όλων των εποχών. Γεννήθηκε στο Mayfield της Αγγλίας το 1857, γιος ενός δασκάλου του χωριού, και πέθανε το 1930. Για δεκαετίες, σχεδίαζε γρίφους για εφημερίδες και περιοδικά, ενώ αργότερα συγκέντρωσε τους περισσότερους σε βιβλία. Αυτός ο γρίφος προέρχεται από το βιβλίο του Amusements in Mathematics (1917).

Ένας ταξιδιώτης πωλητής, που ζει στην πόλη ${\rm A}$, θέλει να επισκεφθεί όλες τις πόλεις από ${\rm B}$ έως ${\rm P}$ μέσα σε μία εβδομάδα, αν και όχι απαραίτητα με αλφαβητική σειρά, και να επιστρέψει στην πόλη ${\rm A}$ στο τέλος. Σχεδιάζει να εισέλθει σε κάθε πόλη ακριβώς μία φορά. Οι κόκκινες γραμμές είναι οι μοναδικοί δρόμοι που συνδέουν τις $16$ πόλεις. 

Ο ταξιδιώτης πωλητής μπορεί να ακολουθήσει μόνο ευθείες διαδρομές μεταξύ δύο πόλεων, χωρίς να στρίβει σε διασταυρώσεις δρόμων. Πόσες διαφορετικές διαδρομές είναι δυνατές;