Given a chess board of N * N, we have to put only rooks on chess board we wants to place some rooks on the chessboard in such a way that the following conditions are satisfied:
- Each square of the board contains at most one rook.
- There are no four rooks forming a rectangle.
- Formally, there should not be any four valid integers r1,c1, r2, c2 (r1≠r2,c1≠c2) such that there are rooks on squares (r1,c1), (r1,c2), (r2,c1) and (r2,c2)
- The number of rooks is at least 8N