Minimize number of rooks in the final configuration in a chess board with $K$ rooks $(1 \leq K \leq N \times N )$

Question

Given $N \times N$ chessboard with $K$ rooks placed on it initially. The initial position of the $K$ rooks is given as the input.

Any rook can move to any other position only if there is an uncaptured rook in that position. Upon the movement, the initial rook on that position will be captured and removed from the chessboard.

We have to find the minimum number of rooks in the board in the final stable configuration when no rook can attack any other node.

There is no specified order in which rooks can make the movement. Any rook can move once or more with the goal of minimizing the number of rooks in the final configuration.

Answer 1

Construct a graph where each rook is a vertex, and there is an edge between two rooks if these rooks are attacking one another.

If the graph is connected, this is easy to see that we can always do a capture without disconnecting the graph, just choose an edge that is not a bridge, or that is a pendant edge.

With this strategy, the minimum number of rooks will be the size of the connected components of this graph, and it is easy to see that we can't do better.