algorithm design techniques at this pointwe have and now the largest distance is so either or but if then which is impossiblesince is no longer in on the other handif then and this is also impossiblesince only appears once in thusthis line of reasoning leaves no solutionso we backtrack since failed to produce solutionwe try if this also failswe give up and report no solution we now have { once againwe have to choose between and is impossiblebecause only has one occurrence of and two would be implied by this choice is possibleso we obtain { the only remaining choice is to assign this works because it leaves emptyand so we have solution { figure shows decision tree representing the actions taken to arrive at the solution instead of labeling the brancheswe have placed the labels in the branchesdestination nodes node with an asterisk indicates that the points chosen are inconsistent with the given distancesnodes with two asterisks have only impossible nodes as childrenand thus represent an incorrect path the pseudocode to implement this algorithm is mostly straightforward the driving routineturnpikeis shown in figure it receives the point array (which need not be initializedand the distance set and if solution is discoveredthen true will be returnedthe answer will be placed in xand will be empty otherwisefalse will be returnedx will be undefinedand the distance set will be untouched the routine sets xn- and xn as described abovealters dand calls the backtracking algorithm place to place the other points we presume that check has already been made to ensure that |dn( )/ the more difficult part is the backtracking algorithmwhich is shown in figure like most backtracking algorithmsthe most convenient implementation is recursive we we have used one-letter variable nameswhich is generally poor stylefor consistency with the worked example we alsofor simplicitydo not give the type of variables finallywe index arrays starting at instead of