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.

Enigma 69

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[1])
    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 = [0] * 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).

    Enigma 69 - Solution

    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     [0]   *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            [8]   *40*     73     116     149     182     214
         9            [0]    38      74     117     164     201       -
        10                   36      75     118     171       -       -
        11                   34     *76*    120     174       -       -
        12                  [32]     74     121     177       -       -
        13                  [24]     72     123       -       -       -
        14                  [16]     72     123       -       -       -
        15                   [8]     72     124       -       -       -
        16                   [0]    [72]    124       -       -       -
        17                          [64]    124       -       -       -
        18                          [56]    126       -       -       -
        19                          [48]    127       -       -       -
        20                          [40]  *[128]*     -       -       -
        21                          [32]   [120]      -       -       -
        22                          [24]   [112]      -       -       -
        23                          [16]   [104]      -       -       -
        24                           [8]    [96]  *[200]*?    -       -
        25                           [0]    [88]      -       -       -
        26                                  [80]      -       -       -
        27                                  [72]      -       -       -
        28                                  [64]      -   *[288]*?    -
        29                                  [56]      -       -       -
        30                                  [48]      -       -       -
        31                                  [40]      -       -       -
        32                                  [32]      -       -   *[392]*?
        33                                  [24]      -       -       -
        34                                  [16]      -       -       -
        35                                   [8]      -       -       -
        36                                   [0]      -       -       -

      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=" "))
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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

%d bloggers like this: