[Update 2-25-2004 - Duh.  I forgot that for each path I could not only flip and rotate it; but also run it forwards AND BACKWARDS, doubling the number of solutions.  Fix is written up below in the solutions section]

Well, well.  Here is the problem that has plagued the ages.  I got the inspiration to solve this problem from my good friend Ben Geesa.  You can see his original project write-up [here].

THE PROBLEM:
Here's the breakdown, given:

THE ANALYSIS:
So, in doing some research on this problem, I find that the basic question it is asking is the computer science problem classified as all-points longest path, or the longest simple cycle problem.  We all know that all-points shortest path is an easily solvable problem in a very easy fashion computationally in O(n²) time.  This isn't bad, where n is the number of balls in the rack.  Well, all-points LONGEST path is much different.  It cannot be solved in O(n²) time; but how long will it take?  How bad is it and what does this tell us about the solution? 

We know there is only a finite number of possibilities, so the problem is bounded, but what is that bound?  Well, the total number of combinations is pretty easy to compute. For our pool ball problem with 15 balls, we can go from any one ball to any other ball.  So there are 15*14 possible first paths.  After that there are only 13 balls left: 15*14*13.  And so on.  So for us we have a total of:15*14*13*12*11*10*9*8*7*6*5*4*3*2*1 = 15! = 1,307,674,368,000 (1.3 trillion paths - that still less than the national debt).  So, the bounding on this problem is n!; which is a problem that grows faster than polynomial time (n^k) where n is the number of elements and k is some constant.  Clearly n! > n^k; so this problem does NOT have a polynomial solution.  This type of problem is classified as intractable, or the very technical term of 'hard'.  Remember, that in computer science, the terms 'easy' and 'hard' actually refer to the mathematical properties of the problem - they are not the relative terms we use to describe the difficulty of learning a skateboard trick or rating how difficult it is to convince a spouse that you are right. :)

So, this problem is a NP-complete problem (has a solution), but is considered hard - which is getting up to the bounds of what we can actually solve on a computer.  Once this type of problem gets up to about 70 nodes, it becomes theoretically unsolvable because it has more computations than atoms in the universe.  But are there any algorithmic shortcuts?  Unfortunately, doing some theory work, we find the longest simple cycle problem has no shortcuts or tricks. You simply must try all the possibilities to ensure the correct solution.  You can come up with heuristics (which I do just to see) but you are not guaranteed the longest path.  There is no way around computing all the path lengths; but as we'll see, the particular properties of this problem help us out a lot.

So, we have 1.3 trillion paths, so we can set about solving it.

THE COMPUTATION

Attempt 1 - naive solution:
First off, I wanted to find out what ball-park the solution is in. Clearly the shortest path is 14, but what is the rough range of the longest path - 20, 50, 100?  So, I wrote up a quick heuristic solution.  I took Dykstra's greedy algorithm (used to find the shortest path) and inverted it to find the longest path.  This method simply takes the longest path, take the next longest path, next longest, etc until you build up a cycle that touches each ball only once.  The solution it comes up with takes all of like 5 milliseconds and gives the solution of:

Path: i - e - l - c - k - a - o - b - n - h - f - g - j - d - m
Length:37.966709
This was interesting, I didn't think it would be so big right off.  However, theory tells us there is likely a longer solution out there; but it gives us a ballpark.

Attempt 2 - Recursive solution:
Ok, the next solution that popped into my head says to do this recursively; trying each path.  Simply start with a dirty and un-optimized C++ version realized about 150,000 paths/sec.  Well, a little calculation tells us that at that rate, we'd need about:
(1,307,674,368,000 / 150,000) / 60 /60 /24 = 100.9 or 101 days of computation time on my P3 1GHZ laptop.  Not only that, it sucked up a good amount of memory space because it needed to do this in a semi-breadth-first search.  At each new level, it needed to keep track of what paths were left.  If we had the following paths, we had to store a bunch of other info:
A (store b,c,d,e,f,g,h,i,j,k,l,m,n,o as not tried yet) -call  B (store c,d,e,f,g,h,i,j,k,l,m,n,o as not tried yet) - call C (store d,e,f,g,h,i,j,k,l,m,n,o as not tried yet) and so forth. 
I had to be very careful about memory leaks because even a 1 byte leak would have sucked up all available memory in 100 days. Well, I wasn't going to keep a process like that running for 1/3 of a year.  There was a lot of memory thrashing, allocating new blocks at each new recursive call.  This also carried a lot of overhead with recursive state saves/restores.  I realized there was probably better solutions.  But I got busy with school and didn't get to work on it for a while.  But my mind churned on it in my free time.

Attempt 3 - Symmetric realizations
I realized there was a ton of symmetry in this problem. You can start with just the balls A, B, D, E and all other starting points are simply just those positions mirrored left to right, or rotated to a different corner. This takes our solution down to 4*14! which is: 348,713,164,800 - only 350 million paths instead of 1.5 trillion.  There are lots of other symmetric optimizations you can do from there, but I stopped with that one because it was easiest to code up and removed a ton of the work already.  With our old program, we could solve this problem in: (348,713,164,800 / 150,000) /60/60/24 = 26.9 days.  Better, but still way longer than I wanted to keep it running.
I wondered if there was a systematic way the computer could eliminate duplicated paths; but the record keeping on such a large problem started getting more bulky than seemed worth it.  It would be an interesting optimization experiment. 
Another thought that came to mind is that we compute some paths of the balls again and again.  What if we started building up paths, walking thru and eliminated duplicates or using the pre-computed paths we've already done.  But again, there isn't a clear way to leverage this advantage without costing lots of memory for record keeping and searching costs.

Attempt 4 - The dull approach that works best.
I was losing a lot of compute time because of the overhead of call stacks and memory thrashing.  What I needed was a faster solution.  I started by optimizing the free lists at each level to be a bit field in a single 16-bit integer instead of an array of free elements. I also made all the path-length calculations integer based instead of floating points, all obtained from a  pre-computed distance table; so calculations turned into constant time lookups with integer additions. Then, I removed the recursion and made it simply a bunch of nested FOR loops.  This let me introduce the symmetric observations I made above more easily because I didn't need to keep track of which level of recursion I was in.  By removing recursion, there was no more memory allocating because there were no calls stacks being created.  Because the free-list of paths was stored in a single integer at each level, checking for free elements became simple bit twiddling on an array of 15 statically allocated integers - which is way faster than searches in lists.  Well, roll all this into one project and do some more optimization and things get much faster.  On top of that, I made the app multi-threaded so that I could divide and conquer on multiple processors if available.  Well, with this new approach on a single-processor P3 1GHZ laptop, I got the following processing numbers:
Paths/sec: 5,000,000 on average.  5 million paths/second, not bad!
Total computation time: (348,713,164,800 / 5,000,000 ) / 60/ 60 = 19.37 hours.  Way better, and now being threaded I could set the priority settings on the thread so I could use the machine for my normal work or crank it up to full speed overnight.  Also, there is no memory thrashing and everything fits nicely in the processor cache with no swapping.  It's about as fast as it gets. This just goes to show you that some stupid FOR loops are faster than more complicated methods.  As an interesting side note, I tried little optimizations like searching for free paths from both directions, which should have made finding free paths twice as fast; but it actually slowed things down instead of speeding them up.  This is due to the acceleration and look-ahead nature of the Intel processors. If you violate these linear execution and data manipulation rules, it actual costs you more to because the processor has mis-predicted  the look-ahead work and must throw it away as well and start up another path.

Solution (spoiler alert):
So, press go and wait.  I had my app well instrumented and could watch the progress.  My calculation of 19 hours was pretty close: I got a final solution after 18:45:14 h/m/s of computation. It is important to note, that if you find one solution in this problem set, you have immediately found 12.  Because the problem is symmetrical, you can rotate the solution by 60 or 120 degrees, flip it on each axis of rotation AND run it backwards on each turn. As it turns out, there were two unique (non-mirror/rotated) solutions to this problem.  Very interesting:
 

Length: 40.316002
Path: 10-3-12-2-14-1-13-6-11-0-8-5-4-9-7
and it's mirrors:
Path: 10-1-13-2-14-3-12-7-9-4-5-8-0-11-6
Path: 6-13-1-11-0-8-5-7-9-4-12-3-14-2-10
Path: 6-8-5-11-0-13-1-10-2-14-3-12-4-9-7
Path: 7-5-8-9-4-12-3-10-2-14-1-13-0-11-6
Path: 7-12-3-9-4-5-8-6-11-0-13-1-14-2-10
And then take each one backwards - I'll leave that to you.

Length: 40.316002
Path 10-2-14-3-12-7-9-4-5-8-0-11-1-13-6
and it's mirrors:
Path: 10-2-14-1-13-6-11-0-8-5-4-9-3-12-7
Path: 6-11-0-12-1-10-2-14-3-12-4-9-8-5-7
Path: 6-11-0-8-5-7-9-4-12-3-14-2-13-1-10
Path: 7-9-4-5-8-6-11-0-13-1-14-2-12-3-10
Path: 7-9-4-12-3-10-2-14-1-13-0-11-5-8-6
And then take each one backwards - I'll leave that to you again.

So, the  total number of paths that are the longest, because of symmetry, mirrors, and forwards/backwards is 24, all having 40.316002 units in length. And that is that.  Hope you enjoyed it.