Hamilton called his problem of finding a route through the vertices
of a icosahedron the
Icosian game.
A similar problem was posed by Euler: Is it possible for a knight
to visit every square of a chessboard without visiting any square twice?
The problem of finding the shortest circuit in a graph that visits
each city exactly once is the traveling salesman problem (TSP).
Here is a page on the
history
of the TSP, with pictures (including one involving Car 54
and one of the optimal tour for a graph with 13,509 cities).
This is part of a larger site at Georgia Tech on the
TSP.
Two further references for this problem are
TSPBIB
and
Vasek Chvatal's
page on the TSP.
Instances of TSP can be obtained from the
TSPLIB.
