Trouble Understanding Counting Problem

Question

Recall that in chess a queen attacks any square that is on a straight line (horizontally, vertically, or diagonally). Suppose a queen "attacks" the square it occupies. What is the smallest number of queens required to attack all of the squares of a 6x6 chessboard?

Edit: In my original post, I'd asked what "attacking" a square means, but that's been clarified thanks to the comment by Brian M. Scott. Anyway, the answer I got was 4 queens, but I'm not sure how to prove this case is the absolute minimum number of pieces needed. How do you solve this rigorously? I just placed a piece in a corner and worked it out piece-by-piece but I'm sure that is both an inefficient and non-rigorous solution.

Thanks

Edit 2: The solution is found here: http://www.puzzles.com/puzzleplayground/ThreeQueens/ThreeQueensSol.htm

The answer is 3, but I have no idea how to arrive at that solution other than guessing and checking. Is there a clever algorithm you can reiterate to arrive at this value?

Answer 1

It’s not hard to do it with four queens, two side-by-side in the centre and two in opposite corners, so the natural question is whether it can be done with fewer. A central queen attacks the largest number of squares, so it’s tempting to start with one, but after having no luck with such arrangements I decided to try starting with a corner queen to see if I could take advantage of the very obvious symmetry of the resulting position, with the board cut down to a $5\times 5$ board missing a diagonal. It was immediately apparent that a queen placed on one of the $\color{red}\times$ squares below would attack all but two of the previously unattacked squares above the diagonal.

$$\begin{array}{|c|c|c|c|c|c|} \hline \times&\bullet&\bullet&\bullet&\bullet&\bullet\\ \hline \bullet&\bullet&&&&\\ \hline \bullet&&\bullet&\color{red}\times&\color{red}\times&\\ \hline \bullet&&&\bullet&\color{red}\times&\\ \hline \bullet&&&&\bullet&\\ \hline \bullet&&&&&\bullet\\ \hline \end{array}$$

The trick would then be to do something similar below the diagonal, and to do so in such a way that the queen below the diagonal attacked the squares above the diagonal that the queen above the diagonal could not reach, and vice versa. At that point it required very little experimentation to come up with this:

$$\begin{array}{|c|c|c|c|c|c|} \hline \times&\bullet&\bullet&\bullet&\bullet&\bullet\\ \hline \bullet&\bullet&\color{blue}\bullet&\color{red}\bullet&\color{red}\bullet&\color{red}\bullet\\ \hline \bullet&\color{red}\bullet&\bullet&\color{red}\bullet&\color{red}\times&\color{red}\bullet\\ \hline \bullet&\color{blue}\bullet&\color{blue}\bullet&\bullet&\color{red}\bullet&\color{red}\bullet\\ \hline \bullet&\color{blue}\bullet&\color{blue}\times&\color{blue}\bullet&\bullet&\color{red}\bullet\\ \hline \bullet&\color{red}\bullet&\color{blue}\bullet&\color{blue}\bullet&\color{red}\bullet&\bullet\\ \hline \end{array}$$

Here each square except the one with the blue queen is colored according to the first queen to attack it (in the order black-red-blue).

It only remains to show that two queens do not suffice. A queen attacks a total of $11$ squares in her own row and column, and in addition she attacks $5,7$, or $9$ more squares on her diagonal(s), depending on whether she’s on an edge, one row in from an edge, or central.

Two queens can attack at most $11+11-2=20$ squares along rows and columns, since at least two squares must be attacked by both of them. This leaves $16$ squares that must be attacked along diagonals. Since $5+9=14<16$, neither queen can be on an edge of the board. But a queen not on an edge square attacks only $8$ edge squares, so if neither of two queens is on an edge, the queens can attack only $16$ of the $20$ edge squares. Thus, no arrangement of just two queens can attack every square.