The Sling Blade Runner puzzle is my favorite. Been hacking on and off on it for the past three years. Every six months or so I come back and spent a few weekends on it. So many different ways to approach the problem. Genetic algorithms, graph simplification, splitting, and pruning algorithms, graph key node analysis, all sorts of different traveling salesman approaches, not to mention creating super small/fast brute force, there is always something new to try against it. Even generated various images of the graph with dot just for kicks. If anyone is looking for a problem to try this would be one I recommend to try. Going by number of movies you should have no problem getting more then 200 in length and with something better (or luck) over 300. Have something really good and you can get above 320 :)
You might want to check your code. Since each title can be used at most once in the solution and there are 6589 movies, it would seem that there are at most 3294 possible solutions, no?
