Solution
The correct solution was found by Joseph DeVincentis and Philippe Fondanaiche.
The first three submitters all suggested that 8 was the answer. In fact, it is 9. DeVincentis found the 9 and wrote a program based on an exhaustive backtracking search to find all examples.
Here are the points:
{{0, 0}, {0, 1}, {1, 2}, {1, 0}, {2, 2}, {0, 4}, {3, 4}, {2, 1}, {4, 4}, {4, 0}}
Note that the nine squared distances here are {1, 2, 4, 5, 8, 9, 10, 13, 16}, which are the first nine sums of two squares. This problem, originally due to Gordon Hamilton, has been well studied, including a mention on a recent New York Times blog.
Prior to my posting, the best known results were up to 9 × 9. But DeVincentis's work extended this to 12 × 12. Here are images of optimal examples for all cases up to 12 × 12 also available at the first link above, to the On-Line Encyclopedia of Integer Sequences®:
[Back to Problem 1215]
© Copyright 2015 Stan Wagon. Reproduced with permission.