title: Solver for TSP-like Puzzle, perhaps in Javascript
body: <p>I have created a puzzle which is a derivative of the travelling salesman problem, which I call Trace Perfect.</p>
  
  <p>It is essentially an undirected graph with weighted edges. The goal is to traverse every edge at least once in any direction using minimal weight (unlike classical TSP where the goal is to visit every vertex using minimal weight).</p>
  
  <p>As a final twist, an edge is assigned two weights, one for each direction of traversal.</p>
  
  <p>I create a new puzzle instance everyday and publish it through a JSON interface.</p>
  
  <p>Now I know TSP is NP-hard. But my puzzles typically have only a good handful of edges and vertices. After all they need to be humanly solvable. So a brute force with basic optimization might be good enough.</p>
  
  <p>I would like to develop some (Javascript?) code that retrieves the puzzle from the server, and solves with an algorithm in a reasonable amount of time. Additionally, it may even post the solution to the server to be registered in the leader board.</p>
  
  <p>I have written a basic brute force solver for it in Java using my back-end Java model on the server, but the code is too fat and runs out of heap-space quick, as expected.</p>
  
  <p>Is a Javascript solver possible and feasible?</p>
  
  <p>The JSON API is simple. You can find it at: <a href="http://service.traceperfect.com/api/stov?pdate=20110218" rel="nofollow">http://service.traceperfect.com/api/stov?pdate=20110218</a> where pdate is the date for the puzzle in yyyyMMdd format.</p>
  
  <p>Basically a puzzle has many lines. Each line has two vertices (A and B). Each line has two weights (timeA for when traversing A -> B, and timeB for when traversing B -> A). And this should be all you need to construct a graph data structure. All other properties in the JSON objects are for visual purposes.</p>
  
  <p>If you want to become familiar with the puzzle, you can play it through a flash client at <a href="http://www.TracePerfect.com/" rel="nofollow">http://www.TracePerfect.com/</a></p>
  
  <p>If anyone is interested in implementing a solver for themselves, then I will post detail about the API for submitting the solution to the server, which is also very simple.</p>
  
  <p>Thank you for reading this longish post. I look forward to hear your thoughts about this one.</p>