4
$\begingroup$

I encountered this problem earlier today.

Suppose we have an 8x8 chessboard, and 10 rooks. We fill in some of the squares on the board such that it's impossible to place the 10 rooks on empty squares so that every empty square on the board either contains a rook or is being attacked by a rook (Rooks cannot attack through a filled in square). Find the minimum number of squares we must fill in.

It seems like the answer is 5 (as stated below in the answers) Is there a nice combinatorial proof to this result? Can we generalize this to other numbers of rooks (e.g. 16)?

$\endgroup$
2
  • 1
    $\begingroup$ You mean "it's possible to place ...", right ? Also, it would be helpful if you show your solution. $\endgroup$
    – Peter
    Nov 16, 2017 at 21:31
  • $\begingroup$ What happens if you fill in the squares in the main diagonals? Don't you need at least three rooks in each of the remaining wedges? I must be misunderstanding the question. $\endgroup$
    – Brian Tung
    Nov 16, 2017 at 21:39

1 Answer 1

Reset to default
2
$\begingroup$

I can do it with $5$. Fill in $a2,b1,a4,b3,c2$ and you isolate $a1,a3,b2$. You have to fill those with rooks but still need eight for the main area.

$\endgroup$

You must log in to answer this question.

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