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]

Advertisements

2 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.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: