The following seemingly trivial number puzzle devised by Cihan Altay and found at Ed Pegg Jr.'s superlative recreational mathematics site www.mathpuzzle.com turns out to have far-reaching consequences. The original puzzle is in Turkish and may be found at www.otuzoyun.com/yarisma/oyun16.html.

In the start position above zero touches 2 squares from other numbers, 1 touches 3 squares from other numbers, 2 touches 4 squares from other numbers, and so on to 9, which touches 4 squares from other numbers. If you multiplied each number by the number of squares it touched, and summed the result, you'd get 0x2 + 1x3 + 2x4 + 3x6 + 4x7 + 5x8 + 6x5 + 7x6 + 8x9 + 9x4 = 277. Rearrange the numbers to maximize this score.

A Java applet to experiment with the puzzle is available here. An equally interesting and difficult puzzle is to find the minimum score. The reader is encouraged to devise a heuristic to produce a "good" solution before attempting the optimization outlined below. An ingenious heuristic by Greg Dulli gives a near optimal solution and is described at http://www.mathpuzzle.com/0123456789.htm.

The Traveling Salesperson-like nature of the puzzle becomes apparent when we define subscripts S=0..9 and variables x_ij=1 if digit i is to the immediate left of digit j and 0 otherwise. Also n_ij is the number of squares touching if digit i is to the immediate left of digit j.

The objective is to maximize the score

Finally

The above formulation is not quite the standard textbook version of the TSP problem where the salesperson is expected to return to the city from which the tour originated. This would be equivalent to the above puzzle with the numbers arranged on a circle where the first and last digits touch each other.

Xpress-MP code to implement the model is here and an Excel spreadsheet version is here. Note that the Premium Solver is required to solve the spreadsheet model.

Another puzzle taken from The Puzzling World of Barry R. Clarke is superficially dissimilar to Altay's puzzle but closer inspection reveals the common underlying structure.

The prisoner sat alone in his cell staring through the bars at the six doors to the guardroom beyond them. Suddenly, there was the sound of footsteps. One guard came in through door A and a second entered through door F. They unlocked the cell door. "We shall set you free," said one of the guards, "but first you must pass through all six doors, each door once only, in the correct order. Three are entrances only and three are exits only. Door A must be followed by door B or E; B by C or E; C by D or F; D by A or F; E by B or D; and F by C or D." With that the guards left through door B. In what order must the prisoner pass through the doors?

Define variables x_ij = 1 if door i is followed by door j and 0 otherwise. Once again we have a TSP problem albeit with added constraints, firstly to model the specified conditions and secondly to ensure that exits and entrances are traversed alternately. The latter may be achieved by defining binary variables t_i=0 if door i is an entrance and 1 if door i is an exit. Then

ensures that if x_ij=1 then t_i or t_j=1 but not both. A complete annotated Xpress-MP model is here.

Many real world applications of the TSP are given in Lawler et al and a useful web resource is http://www.math.princeton.edu/tsp/index.html.

Charles Whitney describes an interesting instance of a TSP in Statistics: A Guide to the Unknown. A space telescope is powered by small gas jets controlled from the ground and although fuel consumption is small it is very expensive to refuel. It is therefore essential to use fuel as efficiently as possible. The identification of a sequence of "visitations" to photograph a list of celestial objects with minimum fuel consumption is a TSP and identical in structure to the above puzzles. The "far-reaching consequences" of Altay's puzzle therefore involve distances measured in billions of light years.

Acknowledgement

The author would like to thank Erhan Erkut for his enthusiastic review of the article and for the many useful observations and comments that were incorporated into the finished work.

References

Lawler, Lenstra, Rinnooy Kan, Shmoys (1985), The Traveling Salesman Problem, Wiley

Tanur, J.M., Mosteller, F. et al (1989), Statistics: A Guide to the Unknown, Duxbury Press, 3rd Edition.

^ã INFORMS