# Minimum Cell Changes to Ensure Unique Numbers in Each Row and Column of an $n \times n$ Table

We have an $$n \times n$$ table, and in each cell of the table, there is a number from $$1$$ to $$2n$$. We want to change the numbers in some of the cells and replace them with other numbers from $$1$$ to $$2n$$ such that in the end, all the numbers in each row and each column are distinct. What is the minimum number of cells we need to change?

I have tried using dynamic programming and assumed the subproblems are $$i\times i$$ minors of the grid. However, I couldn't make significant progress with this approach. I also attempted to reduce the problem to graph problems, such as matchings, but again, I didn't succeed in finding a solution.

Any hints or help would be immensely valuable to me.

• Do you care more about theoretical complexity or practical running time on real-world instances? If the latter, what are typical values for $n$ and for the number of cells that must be changed?
– D.W.
Commented Jun 19 at 9:09
• @D.W. Constraints on $n$ are $1\leq n \leq 300$. Commented Jun 19 at 14:04

### Hint 1

If we have a cell $$a_{i,j}$$ which is duplicate to some other cell $$a_{i, j_1}$$ in its row, and some other cell $$a_{i_1, j}$$ in its column; we can always remove this duplicacy by only changing $$a_{i,j}$$. This is because the maximum number of unique numbers in the row $$\cup$$ column are $$2(n-1)$$ and we can select from $$2n$$ numbers, leaving us with a choice of atleast $$2$$ numbers.

### Hint 2

Following the above hint, the crux of the problem remains on how to optimize number of changes on $$(i, j)$$'s where $$a_{i,j}$$ is duplicate both in the row and column. If the frequency of number $$k$$ in row $$i$$ is $$f^r_{i, k}$$ and in column $$j$$ it is $$f^c_{j, k}$$, then the answer is

$$\sum_{k=1}^{2n} \left( \sum_{i=1}^{n} \max(f^r_{i, k}-1, 0) + \sum_{j=1}^{n} \max(f^c_{j, k}-1, 0) - g(k) \right)$$

where $$g(k)$$ is some number produced by optimising on the common cells. Note we can't just add all the number of common cells as $$g(k)$$ (take the counter example of $$\begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}$$)

### Hint 3

To compute $$g(k)$$, make a weighted directed graph $$G=(V, E)$$ with $$\begin{split} V&=\{S\} \\ &\cup \{{r_1}, {r_2}, \dots {r_n} \} \\ &\cup \{c_1, c_2, \dots c_n\} \\ &\cup \{T\} \end{split}$$ and $$\begin{split} E&=\{(S, r_i, \max(f^r_{i, k}-1, 0)) : \forall 1\le i \le n\} \\ &\cup \{(r_i, c_j, 1): \forall 1\le i, j \le n \text{ if } a_{i,j} = k\} \\ &\cup \{(c_j, T, \max(f^c_{j, k}-1, 0)) : \forall 1\le j \le n\} \end{split}$$

Then the max flow of this graph is $$g(k)$$

## Example

Consider $$n=5$$ and the table to be $$A = \begin{bmatrix} 1 & 2 & 1 & 2 & 1 \\ 2 & 1 & 1 & 1 & 1 \\ 1 & 2 & 1 & 2 & 1 \\ 3 & 1 & 2 & 9 & 3 \\ 2 & 2 & 2 & 2 & 2 \\ \end{bmatrix}$$

• For $$k\in \{4, 5 ,6 ,7 ,8, 10\}$$, we don't see a single cell $$a_{i,j} =k$$. So $$\begin{split} h(k) &= \sum_{i=1}^{n} \max(f^r_{i, k}-1, 0) + \sum_{j=1}^{n} \max(f^c_{j, k}-1, 0) - g(k) \\ &=0 \end{split}$$

• For $$k=9$$, we see only a single cell $$a_{4,4} = 9$$. So $$h(9) = 0$$ too.

• $$k=3$$ is also trivial with $$h(3) = 1$$

• $$k=2$$'s graph $$G$$ has a max flow of $$6$$ (as seen in the image below) So $$\begin{split} h(2) &= \sum_{i=1}^{n} \max(f^r_{i, k}-1, 0) + \sum_{j=1}^{n} \max(f^c_{j, k}-1, 0) - g(k) \\ &= 6 + 6 - 6 \\ &=6 \end{split}$$

• $$k=1$$'s graph $$G$$ has a max flow of also $$6$$ (as seen in the image below) So $$\begin{split} h(1) &= \sum_{i=1}^{n} \max(f^r_{i, k}-1, 0) + \sum_{j=1}^{n} \max(f^c_{j, k}-1, 0) - g(k) \\ &= 7 + 6 - 6 \\ &=7 \end{split}$$

So total number of changes required is $$7 + 6 + 1 = 14$$, as shown in the below table. $$\begin{bmatrix} \color{red} 4 & 2 & \color{red} 3 & \color{red} 5 & 1 \\ 2 & \color{red} 3 & \color{red} 4 & 1 & \color{red} 5 \\ \color{red} 3 & \color{red} 4 & 1 & 2 & \color{red} 6 \\ \color{red} 5 & 1 & 2 & 9 & 3 \\ \color{red} 1 & \color{red} 5 & \color{red} 6 & \color{red} 3 & 2 \\ \end{bmatrix}$$

## Algorithm runtime analysis

For each number $$k$$, let $$f_k$$ denote the total number of cells $$a_{i, j} =k$$ in the table.

Time complexity of

• Finding $$f^r_{i, k}$$ and $$f^c_{j, k}$$ for all $$i, j, k$$ is $$\mathcal{O}(n^2)$$
• Calculating max flow of graph $$G$$ for $$k$$ using ford fulkerson is $$\mathcal{O}(EF) = \mathcal{O}((n+f_k) f_k)$$ in worst case, but closer to $$\mathcal{O}(n + f_k)$$ in practice.

Then the time complexity is $$\begin{split} T &= \mathcal{O}(n^2) + \sum_{k=1}^{k=2n}( 2 \cdot \mathcal{O}(n) + \mathcal{O}(n + f_k)) \\ &= \mathcal{O}(n^2) + \mathcal{O} \left( \sum_{k=1}^{k=2n} f_k \right) \\ &= \mathcal{O}(n^2) \end{split}$$