Minimum Cell Changes to Ensure Unique Numbers in Each Row and Column of an n×n Table

Question

We have an n×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?

For example assume the input is:

1 1
2 1

The answer is 1.

I have tried using dynamic programming and assumed the subproblems are i×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.

Answer 1

This can be solved as a matching problem.

import networkx as nx

def min_changes (matrix):
    G = nx.Graph()
    for i, row in enumerate(matrix):
        for j, value in enumerate(row):
            # We have up to 5 vertices per cell.
            #
            # This cell as part of row/column:
            #   ("r", i, j), ("c", i, j)
            #
            # Match to these to stay the same.
            #   ("row", i, value), ("col", j, value)
            #
            # Match to these to force resolving a conflict.
            #   ("cr", i, j), ("cc", i, j)

            # We want to match this cell to the existing value.
            # Note, only one cell per row/col can do this to a
            # given value.
            G.add_edge(("r", i, j), ("row", i, value), weight=0)
            G.add_edge(("c", i, j), ("col", j, value), weight=0)

            # Note, matching either of these forces the cell to change.
            G.add_edge(("r", i, j), ("ch", i, j), weight=1)
            G.add_edge(("c", i, j), ("ch", i, j), weight=1)

    # This is the lowest weight matching among all matchings of
    # maximum cardinality.
    #
    # If possible, both "r" and "c" for a cell will match to value.
    # Otherwise one (doesn't matter which) will match to the need
    # to change.
    matches = nx.algorithms.matching.min_weight_matching(G)
    weight = 0
    for n1, n2 in matches:
        edge = G.get_edge_data(n1, n2)
        weight += edge["weight"]
        # Uncomment these to see where conflicts are.
#        if 0 < edge["weight"]:
#            print(" ", n1, n2)
    return weight

And let's test it.

import random
n = 5
for _ in range(3):
    M = [[random.randint(1, 2*n) for j in range(n)]
            for i in range(n)]
    print(M)
    print(min_changes(M))