Problem: arrange integers 1 to 15 in a line, so that every two adjacent numbers sum up to a perfect square.

Solution: all perfect squares in question would be 4,9,16, and 25. For each number, find all other numbers that add up to one of those 4 squres. This form a graph. Start from one vertex, find a Hamilton path. Since 8 and 9 each is connected to one edge, they must be the two ends of the path. Start from either of them. The answer is 8,1,15,10,6,3,13,12,4,5,11,14,2,7,9 or the other way round.

This leads to a Haskell program as follows. I didn’t carefully design the data structure to make it general. But you get the idea:

type Graph a = ([a],[(a,a)])  remove_vertex :: Eq a => Graph a -> a -> Graph a remove_vertex (vs,es) v =     ([v' | v' <- vs, v' /= v],[(i,j) | (i,j) <- es, i /= v, j /= v])  hamilton_path :: Eq a => Graph a -> a -> [[a]] hamilton_path ([v],_) _ = [[v]] hamilton_path g@(_,es) n =     concat [ do { p <- hamilton_path (remove_vertex g n) n' ;                      return (n:p) }              | (n',m) <- es, m==n]  g :: Graph Int g = ([1..15], [(x,y) | x <- [1..15], y <- [1..15],                        x /= y, elem (x+y) [4,9,16,25]])

I tried to solve the same problem in C++ and end up with a much less elegant solution. No wonder I hate managing memory myself.

#include  #include   class graph { protected:   int vertices;   bool** matrix;  public:   graph (int n)   {     vertices = n;     matrix = new bool* [vertices];     for (int i = 0; i < vertices; i ++) {       matrix[i] = new bool [vertices];       for (int j = 0; j < vertices; j ++)         matrix[i][j] = false;     }   }   ~graph ()   {     for (int i = 0; i < vertices; i ++)       delete matrix[i];     delete matrix;   }    int length ()   {     return vertices;   }    void setEdge (int i, int j, bool b)   {     matrix[i][j] = b;     matrix[j][i] = b;   }    bool getEdge (int i, int j)   {     assert (matrix[i][j] == matrix[j][i]);     return matrix[i][j];   }    int* hamilton_path (int start)   {     // allocate memory for the path to be returned.     int* path = new int [vertices];     // allocate memory for the markers.     bool* markers = new bool [vertices];      for (int i = 0; i < vertices; i ++) {       path [i] = 0;       markers [i] = false;     }      // call hp with initial length 0     bool b = hp (start, markers, path, 0);      delete [] markers;     if (b)       return path;     else {       delete [] path;       return NULL;     }   }  protected:   bool hp (int start, bool markers[], int path[], int len)   {     // add start vertex to the path     path [len] = start;      // mark the start vertex     markers [start] = true;      // base case: if all vertices are already in the path, succeed.     if (len >= vertices-1)       return true;      // for each following vertex of the start vertex     for (int i = 0; i < vertices; i ++) {       if (! getEdge(start, i) || markers[i])         continue;       // recursively look for a Hamilton path starting from it       if (hp (i, markers, path, len+1)) {         // if it is successful, return         return true;       }       // otherwise, continue with the next vertex     }      // all vertices are exhausted, undo the marking and fail     markers [start] = false;     return false;   } };  int main () {   // For integer i, we use i-1 as the index in the graph.   graph g = graph(15);   // initialize the graph.   for (int i = 1; i <=15; i ++)     for (int j = 1; j <= 15; j ++)       if (i+j==4 || i+j==9 || i+j == 16 || i+j == 25)         g.setEdge (i-1,j-1,true);       else         g.setEdge (i-1,j-1,false);    int* p = g.hamilton_path (8-1);    if (NULL == p) {     printf ("Problem can not be solved.n");     return 1;   } else {     for (int i = 0; i < g.length(); i ++)       printf ("%d ", p[i]+1);     printf ("n");   }    delete [] p;    return 0; }