Greatest number of non-attacking moves that queens can make on an $n \times n$ chess board.

I'm trying to extend my OEIS sequence A275815: Maximum total number of possible moves that any number of queens of the same color can make on an $n \times n$ chessboard.

I have computed the first five terms by brute force, and examples of each are given below.

For $n \geq 6$, Alec Jones has conjectured that $A275815(n) = 8(n-2)^2$, which is achieved by placing $4n - 4$ queens around the border of the board—but this has not been proven. Alec's heuristic is based on summing the number of queens that can move to each empty square (which is no more than 8) instead of summing the number of moves each individual queen can make.

Any thoughts on how to begin to prove this conjecture?

Examples:

A $2\times 2$ chess board can "host" 4 queen moves:

1. $a1 \to b1$
2. $a1 \to b2$
3. $a2 \to b1$
4. $a2 \to b2$

A $3 \times 3$ board can host 17 moves: (The queen at a3 has three moves, the queen at a2 has four moves, and the queens at b1 and c3 each have five moves.)

A $4 \times 4$ board can host 40 moves:

And a $5 \times 5$ board can host 76 moves:

Here’s a proof/sketch for sufficiently large n. I think $n \geq 4 * 5 + 3 = 23$ for operation (c). You may be able to apply the new scoring to the Lemma, so you then only need (c) to be nonnegative, in which case $2(n-2) - 8 \geq n - 1$, so $n \geq 11$. Also, in the new scoring, diagonals are a bonus, unless it's short, so you may be able to get $2(n-2) - 4 \geq n - 1$, or $n \geq 7$. This is my first post, so I hope it's clear.

The main idea is to look at the queens in each row/col/diagonal and to show that if the arrangement doesn’t satisfy certain properties, then we can locally improve the arrangement, by which I mean that we will find a different arrangement that is not worse. The second key idea is that sometimes, it’s hard to locally improve an arrangement. However, you can then overestimate the score (the score is the number of non-attacking moves) for each arrangement so that the best arrangement has the same score, but in a way that each non-maximal arrangement can now be improved.

There are 3 operations we can apply on a queen in a row/column/diagonal, which we call a slice.

(a) It is sandwiched between 2 queens (not necessarily directly) and we delete it.

(b) It is the last/first queen in that slice, we delete it and add it to its end of the slice.

(c) It is the only queen in that slice, and we delete it and put 2 queens on both ends of that slice.

These operations can be applied simultaneously on a single queen along different slices in the natural way.

Lemma. We can assume there is no row or column with only one queen (or else we can improve the arrangement).

Proof. If there is, then we apply operation (c) in that row or column and in every other slice containing the queen, we apply (a), (b), or (c) as appropriate. Note that (c) increases the score for a row/col by an order of n, i.e. from $n-1$ to $2(n-2)-8$. (a) increases by 2, and (b) can only worsen the score by at most 4 (+1 for that slice, and -5 since now queens can’t move into the edge where the queen was pushed to). Since n is sufficiently large, (c) outweighs (a) and (b), so the arrangement is non-worsened.

Proof of theorem. Suppose a diagonal has $k$ squares. Then, if $k = n$, which we call a long diagonal, or $k = 2$, a short diagonal, we score it normally. $k = 1$ is naturally scored 0. For $k = 3$, we ignore the middle of the diagonal when scoring (so having both ends is 2, one end is 2, and no ends is 0). Otherwise, let the number of queens on the ends of that diagonal be $0 \leq q \leq 2$. We score it as $2(k-2) - 2 + q$ instead. Note that the new score is always better or the same than the original score.

Now, suppose we have a queen not at the edge of the board. (a) always increases the score by 2. For (b), we have a few cases.

1. The slice is a row/col, and the end of the slice is not in a long or short diagonal. Then we get +1 along that slice, +2 from the added queen for the diagonals (unless one of them is the k = 3 diagonal, in which case we only get one diagonal, so +1), and at most -2 along the slice for the new queen, for a total of +1 (or + 0).

2. The slice is a row/col and the end of the slice is in a short diagonal and the queen is not on a long diagonal. Then we get +2 along the slice, +1 from the non-short diagonal, potentially -1 from the short diagonal, and -2 along the edge slice, for a total of +0.

3. The queen is on a long diagonal and the end is on a short diagonal. This is a special case where we look at the combination of some of the operations we apply on that queen. Label the corner D, the queen’s square as A, and the other two squares in the 2x2 defined by A and D as B and C. We now cover all the cases for A, B, C, and D. The ending state is B, C, and D are all occupied and A is unoccupied.

   • B, C are occupied. We get +2 along B’s slice, +2 for C, and at most -1 for D.
   • B, C, D all unoccupied. We get +1 along B’s slice, -1 along the edge slice for B, and +1 for the diagonal B is in (the short BC diagonal doesn’t change). For C, we also get +1 total. For D, we get +1 along the long diagonal, and -2 from the edge slices. Total, we have at least +1.
   • B, C unoccupied, D is occupied. We get +1 along B’s slice, -2 for B’s edge, and +1 for the diagonal B is in. Same for C. For D, we get +2, so overall at least +2.
   • C occupied, B, D are unoccupied. We get +1 along B’s slice, -1 for B’s edge, +1 for the diagonal B is in, and -1 for the short diagonal. We get +2 for (a) on C, and +1 along the long diagonal and -2 along the edges for D. Total is +1.
   • C occupied, B unoccupied, D occupied. We get +1 along B’s slice, -2 for B’s edge, +1 for the diagonal, and -1 for the short diagonal. C is +2 and D is +2. So overall +3.

4. The slice is the long diagonal. We already covered when the queen is one away from the corner in case 3, so now the queen is 2 away. Either way, applying (a) or (b) increases by 2 along the slice, and decreases by at most 2 along the edge slices. So, the total is +0.

With all the cases (note that we didn't need to consider slices that were non-short/long diagonals), we see that we can apply the operations to any queen in the middle to push it to all the edges without worsening the score. But from the Lemma, there’s at least 2 in each row/col, so the whole border except for the corners have queens in them. From there, it is clear that filling in the corners improves the (new) score. So for n sufficiently large, the best is to have all queens along the border, for a total of $8(n-2)^2$ (which has the same score in both systems).

I investigated a similar problem a few years ago as part of my effort to archive the Enigma puzzles from New Scientist magazine.

Enigma 69 (from July 1980) is about determining the maximum number of moves on a 4×4 board, using the minimum number of Queens. The puzzle text implies that the "border configuration" is known to be optimal for an 8×8 board.

I recently revisited this puzzle and refined my algorithm to allow me to fully investigate the 6×6 board, and I can confirm that the maximum number of moves in this case is 128 with 20 Queens (using the "border configuration").

You can see all my results at: [ https://enigmaticcode.wordpress.com/2013/03/10/enigma-69-maximum-queen-moves/ ]

It's worth noting that although 40 moves is indeed the maximal solution for the 4×4 board, it can be achieved with only 6 Queens (it is also achievable with 7 and 8 Queens).

While still being brute force, turning this problem into an integer linear programming problem can fill the gap up to "sufficiently large".

Here is python3 code using the PuLP library (the relevant package is called python3-pulp on debian) that confirms the conjecture for all $n<25$ in less than a minute. It can go higher if needed.

from pulp import *

near = [-1, 0, 1]

dirs = [ (x,y) for x in near for y in near if (x,y) != (0,0) ]

def ray(start, dir, valid):
    res = []
    x,y = start
    dx,dy = dir
    while x in valid and y in valid:
        res.append((x,y))
        x += dx
        y += dy
    return (start,dir,res[1:])

def mq(n):
    print("n =", n)
    prob = LpProblem("Maximize Queen moves", LpMaximize)
    R = range(n)
    positions = [(i,j) for i in R for j in R]
    queen = LpVariable.dicts("Q", positions, 0, 1, LpInteger)
    # queen[pos]=1 iff there is a queen at pos
    rays = [ ray(pos, dir, R) for pos in positions for dir in dirs ]
    rays = [ r for r in rays if r[2] != [] ]
    posdirs = [ (pos,dir) for pos,dir,_ in rays ]
    reach = LpVariable.dicts("R", posdirs, 0, 1, LpInteger)
    # reach[(pos,dir)]=1 iff pos is free and there is a queen in direction dir
    prob += lpSum(reach) # objective function
    for pd in posdirs:
        prob += queen[pd[0]] + reach[pd] <= 1
    for pos,dir,r in rays:
        prob += lpSum([queen[p] for p in r]) - reach[(pos,dir)] >= 0
    prob.solve()
    assert prob.status==LpStatusOptimal, "Couldn't solve"
    print(int(value(prob.objective)), "moves:")
    print()
    for i in R:
        for j in R:
            print(".Q"[int(value(queen[(i,j)]))], end='')
        print()
    print()
    print()

if __name__ == "__main__":
    for i in range(2,25):
        mq(i)

If you want to minimize the number of queens as secondary optimization goal, use something like n**2*lpSum(reach)-lpSum(queen) as objective function.