Given an n times n chess board where some squares are marks not available, we wi
ID: 3572821 • Letter: G
Question
Given an n times n chess board where some squares are marks not available, we wish to find the largest number of available squares such that these available squares do not share any row or any column. That is, each selected square is at a distinct row and a distinct column. Please use the 8 times 8 chess board shown in the following figure to illustrate how to model this problem as a maximum bipartite matching problem. (b) Find the largest set of available squares for the above 8 times 8 chess board such these available squares do not share any row or any column.Explanation / Answer
a)
Yes we can model the given problem as maximum bipartite matching problem. Basically we need to find the squares on the chess board such that the don't share same row/column. It is similar to finding two edges in a bipartite graph with share no endpoint. Here the solution will be implemented in such a way that we check for a given node and then see that whether any other node is there which is not lying on the same column/path and then mark them as visited/not visited to the find the total number of squares.
b)
By using the same model and counting the squares for each iteration we will get maximum of 8 squares in the chess board with don't share row/column.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.