Given an $n$ by $n$ grid of which some of the squares are black and some are white. I'm allowed to mark some of these squares and the question is to prove whether a given grid with given black squares can meet these conditions:
1) Each column has only one marked square.
2) Each row has only one marked square.
3) Only white squares can be marked.
This is similar to how sudoku can only have the same number on only one column and one row. In fact it's an easier problem. However…
I am struggling to figure out an algorithm that reduces this problem to a max flow network problem.
I'm thinking something along the lines of making each square in the grid a node in a graph. Then connect your source point to all the white nodes.
I also believe that in the end the way you prove whether such conditions can be met is by whether or not the max flow through this graph is exactly $n$. Because a solution to the above problem requires that there are exactly $n$ marked squares. Any less means that there was a row or column that doesn't have any white square or that there is no way of adding points that end up in distinct rows/columns.
Best Answer
Suppose you have $n$ rows and $m$ columns. Create $n$ nodes name $R_i$ to represent each row.
Each row can have at most 1 white square, so add 1 edge entering $R_i$ with a capacity of $1$.
If Table entry $T_{i,j}$ is white, add it to the graph. Connect an edge from $R_i$ to $T_{i,j}$ with a capacity $1$. This represents "The row has chosen this cell".
Now we need to represent "and no column is chosen more than once". So add $m$ nodes $C_j$ to the graph to represent the columns. Connect any existing $T_{i, j}$ to $C_j$ and give the column an input equal to how many cells are marked.
Each row can only have 1 marked cell, so add 1 edge to the output of $R_i$ and give it a capacity of $1$ so that it cannot input more than 1 cell.
Add a start node $S$ to feed the rows, and an end node $E$ to absorb the columns. In summary:
$$\text{Vertices} = \{S, R_1, R_2, \dots R_n, T_{1, 1}, \dots \text{For those cells that are white} \dots T_{n, m}, C_1, C_2, \dots C_m, E\}$$
And the directed edges $(\text{From}, \text{To}, \text{Capacity})$ are
$$\begin{array} {c} (S, R_1, 1), (S, R_2, 1), \dots, (S, R_n, 1)\\ \\ (R_1, T_{1,1}, 1), (R_1, T_{1, 2}, 1), \dots, (R_1, T_{1, m}) \\ (R_2, T_{2,1}, 1), (R_2, T_{2, 2}, 1), \dots, (R_2, T_{2, m}) \\ \vdots \\ (R_n, T_{n,1}, 1), (R_n, T_{n, 2}, 1), \dots, (R_n, T_{n, m}) \\ \\ (T_{1,1}, C_1, 1), (T_{2,1}, C_1, 1), \dots, (T_{n, 1}, C_1, 1) \\ (T_{1,2}, C_2, 1), (T_{2,2}, C_2, 1), \dots, (T_{n, 2}, C_2, 1) \\\ \vdots \\ (T_{1,m}, C_m, 1), (T_{2,m}, C_m, 1), \dots, (T_{n, m}, C_m, 1) \\ \\ (C_1, E, 1), (C_2, E, 1), \dots, (C_m, E, 1) \end{array}$$