in reply to Simple but thought-provoking programming tasks [OT]
In the lab where I did my graduate work, there was a post doc who used to give the following problem to those prospective graduate students who were uncertain about their programming chops (and wanted some reassurance on whether they'd be able to handle the work).
Consider a 3-dimensional graph consisting of 27 vertices with coordinates (x, y, z), where each of x, y, and z belongs to the set {0, 1, 2}, and whose edges are the segments of length 1 between any two nodes along the coordinate axes (i.e. the coordinates of the endpoints of each edge differ by 1 at exactly one position). A "path" on this graph is defined as an ordered sequence of vertices such that adjacent vertices in the sequence are neighbors in the graph (i.e. the coordinates of two adjacent vertices in a path differ at exactly one position). A Hamltonian path (HP) on this graph is one that visits each of the 27 vertices exactly once.
The problem is to count exactly all the HPs on this graph.
One further detail had to do with the geometric symmetries of such cubic lattice. In the way the problem was usually posed, all the HPs that could be obtained from a given HP by a 3-D symmetry operation (e.g. flipping the lattice around one of its axes of symmetry, or reflecting through a plane of symmetry, etc.) counted as only one HP. (BTW, accounting for these symmetries is the trickiest aspect of the problem.) However, two HPs that could be obtained from each other by reversing the order of the nodes were to be counted as two different HPs.
the lowliest monk