How many squares can 4 queens control?

Question

Though there is no strict mathematical proof, it has been shown via brute-force that no arrangement of 4 or fewer queens can control every square on a standard 8x8 chessboard.

So, out of the 64 squares on an 8x8 chessboard, what is the maximum number of squares that can be controlled by only 4 queens?

Answer 1

62 is the optimal result, I wrote an (admittedly somewhat hackneyed (and in retrospect not very good)) brute force program in Java which can be found here. It returns that 2 is the smallest number of uncovered squares possible using four queens.

In short, it places four queens on a board, scans the board for each position, and outputs the case with the maximum number of covered squares. Since we're looking at $(8^2)^4\approx 17\mbox{M}$ combinations, this is totally feasible for a regular computer to execute.

The first case my program comes across is:

---

Here's a particular case example of this situation.

From Xynariz' question and answer, we know that the minimum number of queens is five, and that it occurs in this configuration:

Therefore, we want to count the number of squares uniquely covered by each queen (that is, how many squares one and only one queen covers for each queen.)

To do this, we draw a line through each queen. Warning: this gets nasty.

It can be clearly seen that any square with only one line through it is uniquely covered by a queen. Those squares are highlighted with blue on the right. We want to remove the queen that uniquely covers the fewest squares.

You can either follow the lines out from the queens, or count how many blue squares each queen controls. Either way, you'll see that:

• Red covers one square
• Blue covers four squares
• Orange covers six squares
• Purple covers four squares
• Green covers four squares.

Therefore, we should remove the red queen from the grid. Removing the red queen uncovers red's uniquely covered square, as well as the queen's square. As a result, the greatest number of squares that can be covered in this case by four queens is $64-2=62$.

Answer 2

TL;DR: The maximum number of squares that can be covered by 4 queens on a 8x8 board is 62, achievable through 64 different board orientations. By "different" I mean that the mirror image/rotation of one of the orientations does not produce another that is counted.

---

I also used a brute-force approach, using the following Python 2.7 code:

from itertools import combinations as combs

def covered_set(row, col):
    controlled = set()

    for i in range(1,9):
        controlled.add((row, i))

    for i in range(1,9):
        controlled.add((i, col))

    x = 1
    while row + x <= 8 and col + x <= 8:
        controlled.add((row + x, col + x))
        x += 1

    x = 1
    while row - x >= 1 and col - x >= 1:
        controlled.add((row - x, col - x))
        x += 1

    x = 1
    y = 1
    while row + x <= 8 and col - y >= 1:
        controlled.add((row + x, col - y))
        x += 1
        y += 1

    x = 1
    y = 1
    while row - x >= 1 and col + y <= 8:
        controlled.add((row - x, col + y))
        x += 1
        y += 1

    return controlled

max_covered = 0
arrangement = []
for a,b,c,d in combs(range(64), 4):
    row1, col1 = divmod(a, 8)
    row2, col2 = divmod(b, 8)
    row3, col3 = divmod(c, 8)
    row4, col4 = divmod(d, 8)

    controlled = len(covered_set(row1+1, col1+1) |
                     covered_set(row2+1, col2+1) |
                     covered_set(row3+1, col3+1) |
                     covered_set(row4+1, col4+1))

    if controlled > max_covered:
        max_covered = controlled
        arrangement = [((row1+1, col1+1), (row2+1, col2+1), (row3+1, col3+1), (row4+1, col4+1))]
    elif controlled == max_covered:
        arrangement.append(((row1+1, col1+1), (row2+1, col2+1), (row3+1, col3+1), (row4+1, col4+1)))

print max_covered
for v in arrangement:
    print v

Output:

62
((1, 1), (2, 5), (5, 8), (8, 2))
((1, 1), (2, 8), (5, 2), (8, 5))
((1, 1), (2, 8), (5, 4), (6, 5))
((1, 1), (3, 5), (5, 7), (7, 3))
((1, 1), (3, 7), (5, 3), (7, 5))
((1, 1), (4, 5), (5, 6), (6, 4))
((1, 1), (4, 5), (5, 6), (8, 2))
((1, 1), (4, 6), (5, 4), (6, 5))
((1, 2), (2, 6), (5, 1), (6, 5))
((1, 2), (4, 6), (5, 5), (8, 1))
((1, 2), (4, 8), (7, 5), (8, 1))
((1, 3), (2, 7), (5, 2), (6, 6))
((1, 3), (2, 7), (5, 2), (7, 5))
((1, 3), (3, 7), (5, 1), (7, 5))
((1, 4), (2, 8), (5, 3), (6, 7))
((1, 4), (3, 8), (5, 2), (7, 6))
((1, 4), (4, 7), (7, 1), (8, 8))
((1, 5), (2, 1), (5, 6), (6, 2))
((1, 5), (3, 1), (5, 7), (7, 3))
((1, 5), (4, 2), (7, 8), (8, 1))
((1, 6), (2, 2), (5, 7), (6, 3))
((1, 6), (2, 2), (5, 7), (7, 4))
((1, 6), (3, 2), (5, 8), (7, 4))
((1, 7), (2, 3), (5, 8), (6, 4))
((1, 7), (4, 1), (7, 4), (8, 8))
((1, 7), (4, 3), (5, 4), (8, 8))
((1, 8), (2, 1), (5, 5), (6, 4))
((1, 8), (2, 1), (5, 7), (8, 4))
((1, 8), (2, 4), (5, 1), (8, 7))
((1, 8), (3, 2), (5, 6), (7, 4))
((1, 8), (3, 4), (5, 2), (7, 6))
((1, 8), (4, 3), (5, 5), (6, 4))
((1, 8), (4, 4), (5, 3), (6, 5))
((1, 8), (4, 4), (5, 3), (8, 7))
((2, 2), (3, 6), (6, 1), (7, 5))
((2, 2), (4, 7), (6, 1), (7, 5))
((2, 3), (4, 7), (6, 1), (8, 5))
((2, 3), (4, 7), (6, 5), (8, 1))
((2, 4), (3, 8), (5, 2), (7, 7))
((2, 4), (3, 8), (6, 3), (7, 7))
((2, 4), (4, 6), (6, 2), (8, 8))
((2, 4), (4, 7), (7, 2), (8, 6))
((2, 4), (4, 8), (6, 2), (8, 6))
((2, 5), (3, 1), (5, 7), (7, 2))
((2, 5), (3, 1), (6, 6), (7, 2))
((2, 5), (4, 1), (6, 7), (8, 3))
((2, 5), (4, 2), (7, 7), (8, 3))
((2, 5), (4, 3), (6, 7), (8, 1))
((2, 6), (4, 2), (6, 4), (8, 8))
((2, 6), (4, 2), (6, 8), (8, 4))
((2, 7), (3, 3), (6, 8), (7, 4))
((2, 7), (4, 2), (6, 8), (7, 4))
((3, 2), (4, 6), (7, 1), (8, 5))
((3, 3), (4, 7), (7, 2), (8, 6))
((3, 4), (4, 5), (5, 3), (8, 8))
((3, 4), (4, 5), (7, 1), (8, 8))
((3, 4), (4, 6), (5, 5), (8, 1))
((3, 4), (4, 8), (7, 3), (8, 7))
((3, 5), (4, 1), (7, 6), (8, 2))
((3, 5), (4, 3), (5, 4), (8, 8))
((3, 5), (4, 4), (5, 6), (8, 1))
((3, 5), (4, 4), (7, 8), (8, 1))
((3, 6), (4, 2), (7, 7), (8, 3))
((3, 7), (4, 3), (7, 8), (8, 4))

The first line is the maximum number of squares covered, the following lines are the 1-based (row, col) positions of the four queens that achieve the optimal covering.

So, the answer I received is 62, achieved as such (the two squares that are not controlled I have highlighted with a red circle):

Answer 3

Another way that four queens can guard all empty squares but two is:

  a b c d e f g h
8 . q . , . , . , 8 
7 , . , . , q , . 7 
6 . , . , . , . , 6 
5 , . , . , . , . 5 
4 q , . , . , . , 4
3 , . , . q . , . 3
2 . , . , . , p , 2
1 , . , . , . , . 1 
  a b c d e f g h

The four queens guard every empty square except g2 and h1. Therefore, together with a black pawn on g2, they guard every empty square.

Four queens and a knight can guard every empty square, thus:

  a b c d e f g h
8 . , . , . , . , 8 
7 , . , . , . q . 7 
6 . , . q . , . , 6 
5 , . , . , q , . 5 
4 . , . , q , . , 4
3 , . , . , . , . 3
2 . , . , . , . , 2
1 , . n . , . , . 1 
  a b c d e f g h

This solution was published in Gardner, Martin. Wheels, Life and Other Mathematical Amusements. Pub. Freeman. ISBN 0-7167-1588-0, p.191.