I am given a chessboard of size $8*8$. In this chessboard there are two holes at positions $(X1,Y1)$ and $(X2,Y2)$. Now I need to find the maximum number of rooks that can be placed on this chessboard such that no rook threatens another.
Also no two rooks can threaten each other if there is hole between them.
How can I tackle this problem? Please help
NOTE : A hole can occupy only a single cell on the chess board.
Best Answer
For most positions of the holes there seems to be room for 10 rooks.
If the holes are in the same row (not on the edge, not touching each other, and with at least two rows above and below it), then place 7 rooks as
There are then 3 rows and 3 columns left without anything in them yet; put the last 3 rooks there.
If the holes are in different rows and columns (but not on the edge of the board), place 6 rooks as
There will be 4 rows and 4 columns yet unused; place the 4 last rooks there.
These solutions are clearly optimal for their hole placements, because each maximal horizontal or vertical run of available cells on the board contains a rook.
If the holes are too close to the edges (or to each other) for this to work, there's room for fewer rooks. Writing down exact rules for those cases seems to be tedious but doable.
If you just want an algorithm to find the maximum number of rooks rather than actually place them, one way that seems to work is to count the number of different horizontal hole-less runs of cells on the board, and the number of different vertical hole-less runs of cells on the board. The minimum of these two numbers is obviuously an upper bound on the rooks, and it can always be achieved (this I can only show with a tedious case analysis).