Indian Computing Olympiad

Training Material

Advanced Graph Algorithms→Placing Rooks

Given a chess board in which some squares are obstacles (#) and other are holes (O). You have to place the maximum number of rooks on this chess board such that no pair of rooks attack each other.

  1. A rook cannot be placed on a hole.
  2. A rook attacks the row and column on which it is placed. The attacking range of a rook can span a hole, but is blocked by an obstacle.

Here is an example (not maximum!) 

            -------------------------------
           |   |   |   |   |   |   | R |   |
            -------------------------------
           |   | R |   |   |   |   |   |   |
            -------------------------------
           | R | # | R |   |   |   |   |   |
            -------------------------------
           |   |   |   |   |   |   | O |   |
            -------------------------------
           |   |   |   |   | # |   |   |   |
            -------------------------------
           |   |   |   |   | R |   |   |   |
            -------------------------------
           |   |   |   |   |   |   |   |   |
            -------------------------------

Solution

Without obstacles and holes, the solution is N rooks, each on a separate row and column.

Think of a graph where the vertices are the rows and columns of the chessboard. There is an edge between a row and a column if they intersect.

Since we have holes and obstacles, we modify this graph. The vertices are now maximal vertical and horizontal segments between obstacles. There is an edge connecting a vertical and horizontal segment if they intersect at a square that is not a hole.

Notice that this graph has a nice structure—we can separate the vertices into two disjoint sets, rows and columns. All edges go from one set to the other. There is no edge within a set. So this is a bipartite graph.

Each square on the chessboard corresponds to an edge in the graph. If we place a rook at a square, we select the corresponding edge. This rules out choosing any other edge that shares an endpoint with this edge. Let us say that two edges are disjoint if they have no common end points. To place all rooks, we have to choose a set of edges that are disjoint.

In other words, the solution we seek is a maximum matching in a bipartite graph.


Problems related to