Problem Statement

Given an n × m chessboard, try and place as many rooks as possible on the board in such a way that the number of rooks on each row is equal to the number of rooks on each column (it is allowed for two rooks to attack each other). You are prohibited from placing the rook at some given locations on the board.

Source

This problem was an exercise left to the reader on a Topcoder tutorial click.

After many attempts, I am unable to formalise a solution. To be more specific neither was I able to formulate this problem as an instance of max-flow, nor was I able to model it as an instance of min-cut.

My observations

• The total number of rows that contain a rook must be equal to the total number of columns that contain a rook
• Could we possibly binary search for the solution and construct a bipartite graph for each candidate solution in the binary search?