2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$
    – Bram28
    Commented Aug 3, 2018 at 17:46
  • 1
    $\begingroup$ 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 $\endgroup$
    – Hehe xD Kappa 123
    Commented Aug 3, 2018 at 17:51
  • $\begingroup$ Does a rook attack the square it is on? $\endgroup$
    – Ross Millikan
    Commented Aug 3, 2018 at 18:06
  • $\begingroup$ @RossMillikan Yes $\endgroup$
    – Hehe xD Kappa 123
    Commented Aug 3, 2018 at 18:08

1 Answer 1

Reset to default
0
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ Wouldn't the first rook cover $2n-1$ not $m+n-1$, since $m$ should be the number that the rooks cover collectively? $\endgroup$
    – Hehe xD Kappa 123
    Commented Aug 3, 2018 at 18:36
  • $\begingroup$ 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$. $\endgroup$
    – Steven Stadnicki
    Commented Aug 3, 2018 at 18:36
  • $\begingroup$ 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 $\endgroup$
    – Hehe xD Kappa 123
    Commented Aug 3, 2018 at 18:42
  • $\begingroup$ @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. $\endgroup$
    – Ross Millikan
    Commented Aug 3, 2018 at 18:52
  • $\begingroup$ @RossMillikan Sorry about that, I wasn't clear what optimal meant in my question $\endgroup$
    – Hehe xD Kappa 123
    Commented Aug 3, 2018 at 18:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .