12
$\begingroup$

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.

enter image description here

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.

$\endgroup$
8
  • 1
    $\begingroup$ @Taco I think it is clear $\sqrt 5$ $\endgroup$
    – z100
    Nov 19, 2021 at 20:31
  • 1
    $\begingroup$ @Taco Yes, it is usualy called "Pythagorean theorem" :-) $\endgroup$
    – z100
    Nov 19, 2021 at 20:54
  • 2
    $\begingroup$ @z100, well they're right though in that the question doesn't say which distance metric would be used. Though using something other than the usual geometric distance would probably make this relatively trivial... $\endgroup$
    – ilkkachu
    Nov 20, 2021 at 10:16
  • 1
    $\begingroup$ For results in larger grids see this sequence: oeis.org/A193838 $\endgroup$ Nov 22, 2021 at 5:09
  • 1
    $\begingroup$ @DmitryKamenetsky Also A271490 $\endgroup$ Nov 30, 2021 at 19:28

1 Answer 1

13
$\begingroup$

The maximum is

7

enter image description here

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.

$\endgroup$
9
  • $\begingroup$ Row 2 column 5 is directly next to another tile diagonally, same as row 1 columns 1 and 2. Do diagonals not count, or have I misunderstood the question? $\endgroup$ Nov 19, 2021 at 20:39
  • $\begingroup$ The Euclidean distances are $1$ and $\sqrt{2}$. $\endgroup$
    – RobPratt
    Nov 19, 2021 at 20:41
  • $\begingroup$ Ah, okay, so it's just over my head mathematically lol got it 😁 $\endgroup$ Nov 19, 2021 at 20:42
  • 2
    $\begingroup$ You can also place this many pawns on a 7x7 board. In that case, the solution is unique up to rotation/reflection. $\endgroup$ Nov 19, 2021 at 23:09
  • 1
    $\begingroup$ @DanielMathias I confirm your result. $\endgroup$
    – RobPratt
    Nov 19, 2021 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.