0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Richerby Nov 3 '16 at 17:19
  • $\begingroup$ I just added more information to my post! $\endgroup$ – tobinulilo Nov 3 '16 at 17:43
  • $\begingroup$ So how this is different from the standard Queens problem? (Besides no diagonal capture, so only horizontal and vertical is possible) What does ot mean the rook jump over holes? Since you have picked some techniques, what is wrong with them? More or less I see the excersise, but just not clear enough to understand where is the problem. $\endgroup$ – Evil Nov 3 '16 at 20:01
  • 1
    $\begingroup$ @Evil My main problem is how to formulate and write it down. I understand the problem, and I understand what bipartite graph, bipartite matching, and maximum matching are. But how would you write a solution to this problem in a proper way? How can one formulate the solution for a general case of this problem? The rooks can jump over the holes, but they cannot be inside them, that is, if they want to capture another rook, and in front of them there's a hole, they can jump over it. $\endgroup$ – tobinulilo Nov 3 '16 at 20:32
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This does not answer my question at all. It includes everything that I already knew, and you left the part that was specifically my "question" as an "exercise" for myself. If I knew how to carry out the 'exercise' I wouldn't ask a question in the first place. Thank you! $\endgroup$ – tobinulilo Nov 3 '16 at 17:45
  • 1
    $\begingroup$ @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. $\endgroup$ – aelguindy Nov 3 '16 at 17:49
  • $\begingroup$ 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? $\endgroup$ – tobinulilo Nov 3 '16 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.