# Algorithm for placing rooks on an $n\times n$ chessboard such that they attack exactly $m$ squares

Suppose there is a chessboard with dimensions $n\times n$ and you put rooks on the chessboard such that they collectively attack $m$ squares on that chessboard (a rook attacks the square it is on, too). Given $n$ and $m$, how can you determine how many rooks must be placed on the chessboard, and where to put them?

For example, let's say that the board dimensions are $3\times 3$ and you have to cover $9$ squares on the board by placing rooks. To do this, or to simply cover the board with rooks such that there are no safe squares, you can put $3$ rooks in the coordinates $(1,1);(1,2);(1,3)$ on the board (the first number in the coordinate is the column number, the second is the row number). That way, since a rook attacks all squares in the same row and column as where it stands, all $9$ squares are attacked.

But how can you find the optimal coordinates for any $n$ and $m$ with an algorithm?

• Just to clarify: by 'optimal' you mean the least number of rooks, and so the question is what the minimal number of rooks is that have to be used to attack exactly m squares? Also, is it 'at least' m squares? Because for many values of m, it's impossible to attack exactly m squares. E.g. m=4 for that 3x3 board Commented Aug 3, 2018 at 17:46
• Yes, the optimal solution is considered as the least number of rooks, but it isn't at least $m$ squares, the rooks have to attack exactly $m$ squares, for example, if $m$ is 1 and $n$ is 2 there is no solution in this case. @Bram28 Commented Aug 3, 2018 at 17:51
• Does a rook attack the square it is on? Commented Aug 3, 2018 at 18:06
• @RossMillikan Yes Commented Aug 3, 2018 at 18:08

You can just greedily put the rooks down a diagonal until you cover enough squares. The first rook will cover $2n-1$ squares, the next will cover $2n-3$ new ones, then $2n-5$ and so on. For $k$ rooks you will cover $2kn-k^2$ until $k$ becomes $n$. Any way of placing the rooks that doesn't have them in the same row or column will achieve the same number.
Added: If you have rooks in $p$ rows and $q$ columns you will attack $np+nq-pq$ squares. For $n=6$, then you can cover $0,11,16,20,21,24,26,27,28,30,31,32,33,34,35,36$ cells
• Wouldn't the first rook cover $2n-1$ not $m+n-1$, since $m$ should be the number that the rooks cover collectively? Commented Aug 3, 2018 at 18:36
• This seems to miss most of the interest of the problem, though - for instance, when $n=3$ one can achieve $5$, $7$, $8$ or $9$ cells attached, but AFAICT not $6$. Commented Aug 3, 2018 at 18:36
• Also by that method you cannot reach every value of $m$ that can be reached with another way of placing the rooks. For example if $n=4$ and $m=14$, with your method it cannot be solved, but you can solve it by putting the rooks on (1,1);(3,1);(1,2);(3,3) @Ross Millikan Commented Aug 3, 2018 at 18:42
• @HehexDKappa123: I somehow read the board size as $m \times n$, which i have fixed. I took optimal to mean the minimum number of rooks to cover at least a given number of squares. Commented Aug 3, 2018 at 18:52