title: Two salesmen - one always visits the nearest neighbour, the other the farthest
body: <p>Consider this question relative to graph theory:
  Let <strong>G</strong> a complete (every vertex is connected to all the other vertices) non-directed graph of size <strong>N x N</strong>. Two "salesmen" travel this way: the first always visits the nearest non visited vertex, the second the farthest, until they have both visited all the vertices. We must generate a matrix of distances and the starting points for the two salesmen (they can be different) such that:</p>
  
  <ul>
  <li>All the distances are unique Edit: <strong>positive integers</strong></li>
  <li>The distance from a vertex to itself is always 0.</li>
  <li>The difference between the total distance covered by the two salesmen must be a specific number, <strong><em>D</em></strong>.   </li>
  <li>The distance from A to B is equal to the distance from B to A</li>
  </ul>
  
  <p>What efficient algorithms cn be useful to help me? I can only think of backtracking, but I don't see any way to reduce the work to be done by the program.</p>