# Trouble Understanding Counting Problem

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?

• A queen attacks a square if the queen is on that square or can reach it in one move on an otherwise empty board. Yes, it’s asking for the smallest number of queens that can reach every square in at most one move (where we assume that a queen can reach the square on which she stands). Apr 1, 2015 at 5:08
• See here for $8\times 8$ board. Apr 1, 2015 at 5:11
• Ok, thanks guys for the clarification. Not sure why someone downvoted when I just had a simple question lol but ok. Also, thanks martin for the link. Apr 1, 2015 at 5:13
• So would it be a good idea to start with one piece in the corner? Is there a clever way to use a strategy such as casework? If I were to find a case that works, how can I be sure that it is the minimum number of pieces possible? Apr 1, 2015 at 5:14

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.