Place maximum Rooks on a chessboard 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.
 A: 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
      R
  R
R o R o R
      R
  R

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
  R
R o R
  R o R
    R

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).
A: Here is the drawing I meant to make for ten rooks.(holes are yellow and rooks are black)

A: We can get an algorithm to determine the maximum number of rooks
by considering attacks along ranks (parallel to one axis of the board)
separately from attacks along files (parallel to the other axis).
So first consider only attacks along ranks.
A rank with a single hole in it can still hold only one rook if the hole
is at either end of the rank, but can hold two rooks if the hole
is not at an end of the rank.
So if the holes are on two different ranks, determine the number of rooks
($1$ or $2$) that can be placed on the rank of the first hole,
add the number of rooks that can be placed on the rank of the second hole,
and then add $6$ (one rook on each of the remaining ranks).
This is the maximum number of rooks that can be placed without
an attack along a rank.
If the holes are in the same rank, the number of rooks that can be
placed on that rank depends on the positions of the holes as follows:


*

*Two holes adjacent to each other at one end of the rank: $1$ rook.

*Two holes adjacent to each other but not at either end of the rank: $2$ rooks.

*A hole at each end of the rank: $1$ rook.

*A hole at one end of the rank, the other hole neither at the other end nor adjacent to the first hole: $2$ rooks.

*Two holes, neither of which is adjacent to either end of the rank nor to the other hole: $3$ rooks.


Add $7$ to this number (one rook in each remaining rank) to obtain
the maximum number of rooks that can be placed without an attack
along a rank.
This is an algorithm for finding $R(S)$, the maximum number of rooks
that can be placed on a two-hole board $S$ without allowing
attacks along ranks.
Now perform the same steps again, but substituting "file" every time
the word "rank" appears, to find $F(S)$, the maximum number of rooks
that can be placed on a two-hole board $S$ without allowing
attacks along files.
The maximum number of rooks that can be placed on a board with two
holes in configuration $S$ is $\min\{R(S), F(S)\}$.

With a little thought, the rank and file parts of this algorithm can be
consolidated into a single set of criteria giving the maximum
number of rooks that can be placed:


*

*Both holes on the same edge of the board, or holes on opposite edges of the board: $8$ rooks.

*A hole on an edge of the board and a second hole adjacent to the first: $8$ rooks.

*At least one hole on an edge of the board, but neither of the two cases above is true: $9$ rooks.

*Two holes adjacent to each other, but neither is on any edge of the board: $9$ rooks.

*None of the above cases is true: $10$ rooks.



The rank-and-file algorithm can be abstracted to give the maximum number of rooks placed on an $n\times n$ chessboard with $m$ holes in configuration $S$.
Examine each rank. If there are no holes then the rank can hold one rook
without attack along a rank. If there are holes, they "cut" the rank
into one or more connected sets of squares ("pieces").
(An example of "cutting into one piece" occurs when all the holes are
in consecutive positions at one end of the rank.)
The number of pieces is the number of rooks that can be placed on the rank without attack along a rank.
Add up the number of rooks for each rank to obtain $R(S)$.
Using a similar algorithm for each file, add up the number of rooks for each file to obtain $F(S)$.
The final answer is  $\min\{R(S), F(S)\}$.
A: Consider the generalisation of the problem, place the maximum number of rooks in an m X n board with some given squares cut out.
This problem can be reduced to bipartite matching with the following construction:
Two sets of vertices A and B.
Vertices in A represent columns such that no two rooks placed in different columns attack along the column line. So if there is a square cut in a column, the two vertices will be present in A corresponding to the two partitions of column. 
In particular each cut square create a new vertex in A, so there will be (n+k) vertices in A.
Similarly construct B for rows, there will be (m+k) vertices.
There is an edge from u in A to v in B if column corresponding to u and row corresponding to v intersect.
The maximum matching in this bipartite graph gives the max number of rooks that can be placed which can be efficiently solved using blocking flow in O(E*sqrt(V)) is E and V are the number of edges and vertices respectively.
