Non-attacking “brooks” on a periodic chess board

Question

Here’s a twist on the classic puzzle of non-attacking rooks on a chess board.

A periodic chess board is the same as the usual 8×8 chess board except that pieces can move beyond the boundary and come back on the the other side, like in pac-man (or a torus for more mathematically inclined).

A brook is a rook that can also move diagonally NW-SE, but not NE-SW. (I confess I made up the name of this piece by combining bishop and rook, but unlike a bishop, a brook can move only along NW-SE diagonal.)

Now the question: what’s the maximum number of non-attacking brooks you can place on a periodic chess board?

Bonus question: how about an n×n board instead of an 8×8 board?

Answer 1

Rob Pratt's answer shows that

the answer is $n$ for odd $n$.

And ilikecorgis's comment thereupon shows that

the answer is at least $n-1$ for even $n$

(though ILC merely states that their construction works; actual proof is below; for the avoidance of doubt I am not suggesting that ILC didn't know why the construction works or couldn't easily have written down a proof if they'd wanted to).

So what about

verifying that the answer isn't $n$ for even $n$?

Well,

if it were, then the row numbers in which the brooks appear would be a permutation $(a_1,\ldots,a_n)$ of $\{\,1,2,\ldots,n\,\}$ with the property that we never have $a_i-a_j=i-j\pmod n$.

Well, another way of writing that last condition is that

we never have $a_i-j=a_j-j\pmod n$, which means that the numbers $a_i-i$ are equal mod $n$ to $1,2,\ldots n$ in some order, which means that their sum is equal mod $n$ to $1+2+\cdots+n$. Obviously $\sum a_i-i=0$ since the $a_i$ and the $i$ are the same numbers just maybe in a different order, so this means that $n|1+2+\cdots+n=n(n-1)/2$. But if $n$ is even this is $n/2$ times an odd number, which can't possibly be a multiple of $n$.

So

indeed for even $n$ the maximum number of brooks is at most $n-1$.

Let's fill the last little gap by proving that ILC's construction works.

It places brooks at $(1,n)$, $(2,n-1)$, ..., $(n/2,n/2+1)$, (here is where the discontinuity is) $(n/2+1,n/2-1)$, $(n/2+2,n/2-2)$, ..., $(n-1,1)$. We require that the values of $y-x$ all be distinct mod $n$; these are $n-1$, $n-3$, ..., $1$, (discontinuity!) $-2$, $-4$, ..., $2-n$. Mod $n$ that latter group is, equivalently, $n-2$, $n-4$, ..., $2$. Which means that the values of $y-x$ mod $n$ are just a rearrangement of 1,2,...,n-1 and are indeed all different.

So, indeed,

the answer is $n-1$ for even $n$ and $n$ for odd $n$.

Answer 2

Define a graph with a node for each cell and an edge for each pair of attacking cells. The problem is to find a maximum independent set in this graph.

For fixed $n$, you can solve the problem via integer linear programming as follows. Let $C_k$ be the set of cells in clique $k$ (row, column, or wrapped diagonal). Let binary decision variable $x_{ij}$ indicate whether a brook appears in cell $(i,j)$. The problem is to maximize $\sum_i \sum_j x_{ij}$ subject to linear constraints $$\sum_{(i,j)\in C_k} x_{ij} \le 1 \quad \text{for all $k$}$$

For $n=8$, the maximum turns out to be

$7$.

\begin{matrix}1&0&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\\0&0&0&1&0&0&0&0\\0&0&0&0&0&0&0&0\\0&0&0&0&1&0&0&0\end{matrix}

For general $n$,

consideration of the rook moves yields $n$ as an upper bound. The linear programming relaxation attains this bound; explicitly, take $x_{ij}=1/n$ for all $(i,j)$.

For odd $n$, the maximum is

$n$; for example, just place $n$ brooks along the main antidiagonal.

For even $n$, the maximum appears to be

$n-1$.

Here is SAS code:

proc optmodel;
   num n = 8;
   set ROWS = 0..n-1;
   set COLS = ROWS;
   set CELLS = ROWS cross COLS;
   num numCliques init 0;
   set CLIQUES = 1..numCliques;
   set <num,num> CELLS_c {CLIQUES};
   for {i in ROWS} do;
      numCliques = numCliques + 1;
      CELLS_c[numCliques] = {i} cross COLS;
   end;
   for {j in COLS} do;
      numCliques = numCliques + 1;
      CELLS_c[numCliques] = ROWS cross {j};
   end;
   for {m in 0..n-1} do;
      numCliques = numCliques + 1;
      CELLS_c[numCliques] = {<i,j> in CELLS: mod(i-j+n,n) = m};
   end;

   var X {CELLS} binary;
   max NumSelected = sum {<i,j> in CELLS} X[i,j];
   con Clique {c in CLIQUES}:
      sum {<i,j> in CELLS_c[c]} X[i,j] <= 1;

   solve;

   print X;
quit;