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)?

  • 1
    $\begingroup$ You mean "it's possible to place ...", right ? Also, it would be helpful if you show your solution. $\endgroup$ – Peter Nov 16 '17 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 '17 at 21:39

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.