# Enigmatic Code

Programming Enigma Puzzles

## Enigma 69: Maximum Queen moves

From New Scientist #1212, 31st July 1980 [link]

If you place Queens (as many as you like) on an ordinary 8 × 8 chessboard, in such a way that you have the greatest possible number of moves open to you, you will find you cannot do better than put a Queen on each border square. You thus use 28 Queens in all. Each of the 36 unoccupied squares can then be moved to by just 8 Queens. Total moves available: 36 × 8 = 288. And you cannot achieve 288 with fewer than 28 Queens. Suppose I now ask you to do the same on a 4 × 4 board. If you place a Queen on each border square, you will as the diagram shows, achieve 4 × 8 = 32 possible moves. Can you do better? Remember that your prime purpose is to maximise the number of possible moves; subject to that you want to use as few Queens as you can.

How many possible moves can you get on a 4 × 4 board? And how will you place your Queens?

[enigma69]

### 3 responses to “Enigma 69: Maximum Queen moves”

1. Jim Randell 10 March 2013 at 9:38 am

This recursive solution implemented in Python runs in 1.95s for the 4×4 case.

```from itertools import combinations
from enigma import irange, join, printf

import sys
N = 4 if len(sys.argv) < 2 else int(sys.argv)
N2 = N * N
M = N - 1

def move(i, g):
for (x, y) in i:
p = x * N + y
if g[p] == 'Q': break
g[p] += 1

# count the number of possible moves on the board
def moves(qs):
g =  * N2
for q in qs: g[q] = 'Q'
# move each queen
for q in qs:
(x, y) = divmod(q, N)
move(((x - i, y) for i in irange(1, x)), g)
move(((x + i, y) for i in irange(1, M - x)), g)
move(((x, y - i) for i in irange(1, y)), g)
move(((x, y + i) for i in irange(1, M - y)), g)
move(((x - i, y - i) for i in irange(1, min(x, y))), g)
move(((x - i, y + i) for i in irange(1, min(x, M - y))), g)
move(((x + i, y + i) for i in irange(1, min(M - x, M - y))), g)
move(((x + i, y - i) for i in irange(1, min(M - x, y))), g)
return sum(i for i in g if i != 'Q'), g

# find the maximum number of moves (v), and then minimum number of queens (q)
(v, q, d) = (0, 0, [])

# choose n queens
for n in irange(1, N2 - 1):
# max possible moves for k empty squares is 8k, so stop if we've reached that
m = 8 * (N2 - n)
if (v, -n) >= (m, -q): break
printf("checking {n} queens, current best = {v} with {q} queens")
for qs in combinations(irange(0, N2 - 1), n):
(r, g) = moves(qs)
if (r, -n) > (v, -q):
printf("new best = {r} with {n} queens [{g}]", g=join(g, sep=' '))
(v, q, d) = (r, n, g)
if r == m: break # found max possible moves

printf("maximum moves = {v} with {q} queens [{d}]", d=join(d, sep=' '))
```

Solution: On a 4×4 board the maximum number of moves achievable is 40, using 6 Queens. An example layout is shown below (rotations and reflections of the this solution will also work). 40 moves is also achievable with 7 or 8 Queens.

This algorithm is OK for solving a 4×4 board, but it quickly gets bogged down on larger boards, as it considers each possible combination of placing n Queens for values of n from 1 to N² (on an N×N board). For a 5×5 board this takes 15 minutes (the answer is 76 moves, using 11 Queens). So I was unable to verify the given solution for an 8×8 board using this program.

If the strategy of placing queens on the border squares for N>5 produces the best solution we get:

```N=2: 2 queens, 4 moves [Q Q / 2 2]
N=3: 4 queens, 17 moves [Q Q 3 / 4 4 Q / Q 3 3]
N=4: 6 queens, 40 moves [Q Q 5 Q / 5 4 4 Q / Q 4 4 4 / 3 4 Q 3]
N=5: 11 queens, 76 moves [3 Q Q Q 3 / Q 6 8 6 Q / 5 7 Q 7 5 / Q 6 8 6 Q / 3 Q Q Q 3]
N=6: (20 queens, 128 moves [Q Q Q Q Q Q / Q 8 8 8 8 Q / (x4) / Q Q Q Q Q Q]) ???
N=7: (24 queens, 200 moves [Q Q Q Q Q Q Q / Q 8 8 8 8 8 Q / (x5) / Q Q Q Q Q Q Q]) ???
N=8: (28 queens, 288 moves) [Q Q Q Q Q Q Q Q / Q 8 8 8 8 8 8 Q / (x6) / Q Q Q Q Q Q Q Q]
N=k: (4(k-1) queens, 8(k-2)^2 moves)```
• Jim Randell 25 February 2017 at 11:43 am

I wrote a more efficient version of my program (eliminating symmetrically equivalent positions, using bit vectors to store positions on the board and pre-computing moves), which solves the 4×4 board in 189ms and the 5×5 board in 19s, so it is around 150× faster than my original approach. And although the algorithm is still pathologically slow, this is enough to verify that 128 moves is maximal for the 6×6 board using 20 queens in the “border configuration” (with about 14h of CPU time).

Here’s a summary of the maximal number of moves I have computed for various board configurations:

```        2x2    3x3    4x4     5x5     6x6     7x7     8x8     9x9
Q
1      3      8     11      16      19      24      27      32
2     *4*    12     20      28      36      44      52      60
3      3     16     29      40      53      64      77      88
4        *17*    36      52      68      84     100     116
5            16     38      64      83     104     123     144
6            14    *40*     67      96     120     144     168
7            12    *40*     70     109     136     163     192
8               *40*     73     116     149     182     214
9                38      74     117     164     201       -
10                   36      75     118     171       -       -
11                   34     *76*    120     174       -       -
12                       74     121     177       -       -
13                       72     123       -       -       -
14                       72     123       -       -       -
15                        72     124       -       -       -
16                           124       -       -       -
17                              124       -       -       -
18                              126       -       -       -
19                              127       -       -       -
20                            **     -       -       -
21                                   -       -       -
22                                   -       -       -
23                                   -       -       -
24                                 **?    -       -
25                                     -       -       -
26                                        -       -       -
27                                        -       -       -
28                                        -   **?    -
29                                        -       -       -
30                                        -       -       -
31                                        -       -       -
32                                        -       -   **?
33                                        -       -       -
34                                        -       -       -
35                                         -       -       -
36                                         -       -       -```

The maximal number of moves for each board configuration are denoted with asterisks.

Border configurations are denoted with square brackets.

The (presumed) maximal values for the 7×7 and 8×8 boards are marked with a question mark, as these have not been verified by my program.

2. Jim Randell 6 March 2020 at 10:58 am

Here is a solution using the MiniZinc constraint solver, wrapped using the minizinc.py library to format the results. It can be used to confirm the values for 6×6, 7×7, 8×8, 9×9 and larger boards (I used it to check boards up to 32×32).

```from minizinc import MiniZinc
from enigma import arg, sprintf as f, irange, join, printf

N = arg(4, 0, int)
printf("[N={N}]")

# construct the minizinc model
model = MiniZinc(f("""

% size of the grid
int: N = {N};

% positions of queens: <x>, <y> -> t | f
array [1..N, 1..N] of var 0..1: q;

% is there a queen on the path from <x>, <y> in direction <dx>, <dy>
function var 0..1: path(var 1..N: x, var 1..N: y, -1..1: dx, -1..1: dy) =
exists (k in 1..N - 1) (
if x + k * dx > 0 /\ x + k * dx <= N /\ y + k * dy > 0 /\ y + k * dy <= N
then
q[x + k * dx, y + k * dy] = 1
else
false
endif
);

% score for square <x>, <y>
function var 0..8: score(var 1..N: x, var 1..N: y) =
if q[x, y] = 1
then
0
else
% N, E, S, W
path(x, y, 0, -1) + path(x, y, 1, 0) + path(x, y, 0, 1) + path(x, y, -1, 0) +
% NE, SE, SW, NW
path(x, y, 1, -1) + path(x, y, 1, 1) + path(x, y, -1, 1) + path(x, y, -1, -1)
endif;

% total score for the grid
var int: total;
constraint total = sum (x, y in 1..N) (score(x, y));

solve maximize(total);

"""))

# evaluate the model
for (q, t) in model.solve(result="q total", solver="minizinc --solver coin-bc"):
# output the results
q = list(list(q[x][y] for x in irange(1, N)) for y in irange(1, N))
printf("[{n} queens, score = {t}]", n=sum(v.count(1) for v in q))
for r in q:
printf("[ {r} ]", r=join((".Q"[v] for v in r), sep=" "))
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.