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?
This is a well known problem in competitive programming. When you put a rook in a row and a column, you can no longer have any other rooks in that row and in that column. That is, you are matching rows to column, such that each row gets at most one column and each column gets at most one row. Sounds like bipartite matching?
What do the holes represent? Positions where you cannot place rooks. These are row-column pairs that cannot be matched. I will leave it as an exercise for you to figure out what that means in the bipartite graph of rows and columns.