I have a programming problem for which I need help.
You are given an \(N\times N\) chess board (where \(N\leq 10000\) ) which has no pieces on it. On the board there are obstacles (meaning that no piece can be put on the obstacle and no piece can go over the obstacle at any time). Your job is to provide the maximum number of Rooks you can put on the chessboard so that no \(2\) Rooks atack each other.
Explanation: If there is an obstacle between 2 rooks they dont atack each other! For example:
..O R X R O... is a valid combination for 2 of the rooks if O are open spots on the board, R are rooks and X is the obstacle.
PS: Please provide an explanation of the algorithm you are using as well as a proof if you can so I can understand better!! Much appreciated