All distances different on a chess board

Question

Here is a simple formulation for, I believe, a quite difficult problem.

I have played with it, I don't have the answer yet.

The question: How many pawns can you put on a standard 8x8 chess board in such a way that the distances between two pawns are all different?

Needless to say, each pawn must be exactly centered on a square of the board.

Computers are allowed. Without it, it is quite laborious to even check the validity of a solution.

If no proof of optimality is given (answering to "how many") then my vote goes to the solution that has the most pawns on the board.

Answer 1

The maximum is

7

For this solution, the squared distances are

$\{1,2,4,5,9,10,13,16,17,26,29,34,37,40,45,49,53,58,65,85,98\}$

You can solve the problem via integer linear programming as follows. Let binary decision variable $x_{i,j}$ indicate whether a pawn is placed on square $(i,j)$. For each pair $(i_1,j_1)$ and $(i_2,j_2)$, let binary decision variable $y_{i_1,j_1,i_2,j_2}$ indicate whether $x_{i_1,j_1} \land x_{i_2,j_2}$. For each distance $d$, let $P_d$ be the set of pairs $(i_1,j_1)$ and $(i_2,j_2)$ such that $\sqrt{(i_1-i_2)^2+(j_1-j_2)^2}=d$.

The problem is to maximize $\sum_{i,j} x_{i,j}$ subject to \begin{align} x_{i_1,j_1} + x_{i_2,j_2} - 1 &\le y_{i_1,j_1,i_2,j_2} &&\text{for all pairs $(i_1,j_1)$ and $(i_2,j_2)$} \tag1\\ \sum_{(i_1,j_1,i_2,j_2) \in P_d} y_{i_1,j_1,i_2,j_2} &\le 1 &&\text{for all $d$} \tag2 \end{align} Constraint $(1)$ enforces the logical implication $x_{i_1,j_1} \land x_{i_2,j_2} \implies y_{i_1,j_1,i_2,j_2}$. Constraint $(2)$ prevents more than one pair per distance.