# maximum matching in a bipartite graph for solving a chess rook maximization problem

There's an n x n chessboard where some cells are instead holes. I want to have as many rooks as possible in a way that the rooks won't be able to capture each other. Rooks cannot be placed on the holes but can jump over them. How can I solve this problem using the finding maximum matching principle in a bipartite graph?

• What did you try? Where did you get stuck? We're happy to help with conceptual problems but just solving homework-style exercises for you is unlikely to really help. – David Richerby Nov 3 '16 at 17:19
• @tobinulilo Really?! If in a bipartite graph you cannot match two vertices $u, v$, you don't know what that corresponds to? If you don't then you probably do not know what bipartite matching is. Fine, here is the answer, if the cell $(x, y)$ has a hole then there is no edge $(x, y)$ in the bipartite graph, otherwise there is an edge. – aelguindy Nov 3 '16 at 17:49
• This now makes everything much clearer. Thank you very much. I was really confused and could not connect concepts to each other. Basically in the chess/rooks problem, the placement of one rook per row-column pair corresponds to the bipartite matching problem, and then on top of that when we add the holes, we are basically making the problem correspond to the maximum matching in a bipartite graph. Am I correct in that sense? Thus, simply maximizing the n x n chess problem I have described corresponds to finding the maximum matching in an n x n bipartite graph? – tobinulilo Nov 3 '16 at 18:45