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.
On
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:
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:
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)\}$.
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).