25
$\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$
  • 1
    $\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$ – Steven Stadnicki 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$ – Aza 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$ – Paul Burchett 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$ – Brian Hopkins 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
27
$\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$
  • $\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
  • $\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$ – Aza 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$ – Aza Jan 27 '15 at 18:42
11
+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$

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.