30
$\begingroup$

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?

$\endgroup$
5
  • 2
    $\begingroup$ Another interesting question: what pieces can 'fill the gap'? The answers below suggest that a bishop, king, or knight is enough; can a rook or pawn fill in the missing squares? $\endgroup$ May 29 '14 at 2:59
  • $\begingroup$ @Steven Actually, it takes a queen to guarantee all cases. The $(x,y)$ distances between the open spaces have the following possible combinations: $(0,7),(7,0),(4,4),(1,1),(5,5)$. The cases where $\Delta x = \Delta y$ can be covered by a bishop, and may be covered by a pawn if it's $(1,1)$. But $(0,7),(7,0)$ requires a rook or queen, as the open spots are literally across the board from each other. Consider this board, where only the two pawns are safe. $\endgroup$
    – user20
    May 29 '14 at 5:54
  • $\begingroup$ @Steven - Yes. A rook and pawn can both be used. See the above formation of queens arshajii gave, except put a rook on b8 and move the queen to d6 and all squares are covered. This shows a rook can be used in place of the 5th queen. The diagram arshajii gave also clearly shows a Pawn, King, Knight, or Bishop can be used in place of the 5th queen. $\endgroup$ May 29 '14 at 6:08
  • 1
    $\begingroup$ I appreciate the comments in the referenced MO post about whether an exhaustive computational argument constitutes a mathematical proof. Seems Appel and Haaken are still controversial (mathworld.wolfram.com/Four-ColorTheorem.html). $\endgroup$ May 31 '14 at 2:50
  • $\begingroup$ Are you defining that pieces control the square they stand on? $\endgroup$
    – smci
    Oct 17 '14 at 5:51
33
$\begingroup$

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:

enter image description here


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:

enter image description here

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.

enter image description here enter image description here

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

$\endgroup$
4
  • $\begingroup$ The latter part of your answer only establishes a lower bound. - You give no proof that moving one or more queens can not lead to a situation where 63 squares are covered. $\endgroup$
    – Taemyr
    Jan 15 '15 at 12:57
  • 1
    $\begingroup$ @Taemyr It used to be the body of my answer, and I left if for posterity, but you're right, the latter portion is not a complete proof. $\endgroup$
    – user20
    Jan 15 '15 at 15:44
  • $\begingroup$ hastebin link is broken. $\endgroup$
    – Unsigned
    Jan 26 '15 at 21:43
  • $\begingroup$ @Unsigned ...shoot. I thought that was a permanent hosting service. I'm going to see if I can dig up the source code... otherwise I'll outline how it worked. $\endgroup$
    – user20
    Jan 27 '15 at 18:42
16
+100
$\begingroup$

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):

enter image description here

$\endgroup$
0
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.