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))

Answer 2

This algorithm should work:

• Look through each row and column and collect every non-distinct cell.
• While you have non-distinct cells left
  • If you have a cell which has a duplicate in the same row and column, replace it with a number which is not present in that row/column (this is always possible, since there can't be more than 2n-2 other numbers)
  • At some point you only have cells which have duplicates in either the same row or the same column. Arbitrarily replace (k-1) of each (e.g., if you have a row with four 1, replace three of them) by distinct numbers (this is again always possible).

I guess producing an explicit formula for "the minimum number of cells we need to change" given a certain matrix is mostly a question of finding good notation (not sure if you really want this).

And if you are looking for lower/upper bounds how many cells you need to change: Ideally you don't have to change anything, and in the worst case (e.g. a matrix full of 1s) you have to change n*(n-1) cells.

Answer 3

Say we determine a conflict along some column so that M(r1, c) is equal to M(r2, c). The change in one of the cells has the potential to affect its row (r1 or r2), but since the allowed range is up to 2n, we are always guaranteed to have an available value, even if all others in both the associated row and column are already distinct. This means we can make independent choices about which values to change.

Also consider the worst case, where we first change all n-1 values in one row to match all n-1 values in the column of the nth value that we are about to change, preventing us from using those values as candidates for the nth. Even then, we’ve only used n values, but we’re allowed 2n.

What we still need to consider is how many conflicting pairs can one change address, which is illustrated in the example in the question description,

11
21

where the choice of which 1 to change has an effect on the answer. A cell can have an effect on at most 2 conflicting pairs, one for each axis.

We can select cells to change by the priority of how many conflicting pairs they address.

Python code with brute force comparison:

import collections
import random


def get_next(i, j, n):
  if j == n - 1:
    return i + 1, 0
  return i, j + 1
 
 
def is_valid(M, i, j, v):
  for ii in range(i):
    if M[ii][j] == v:
      return False
  for jj in range(j):
    if M[i][jj] == v:
      return False
  return True
 
 
def brute_force(M):
  n = len(M)
 
  def f(i, j, count):
    if i == n:
      return count
 
    curr = M[i][j]
    best = n**2 - 1
 
    for v in range(1, 2*n + 1):
      if is_valid(M, i, j, v):
        M[i][j] = v
        ii, jj = get_next(i, j, n)
        new_count = count + int(
            curr != v)
        best = min(
            best,
            f(ii, jj, new_count))
        M[i][j] = curr
 
    return best
 
  return f(0, 0, 0)


def get_counts(counts_list):
  return sum([
    sum([max(0, c - 1) for c in counts.values()])
        for counts in counts_list])


def f(M):
  n = len(M)
  row_counts = [collections.defaultdict(int) for _ in range(n)]
  col_counts = [collections.defaultdict(int) for _ in range(n)]

  for i in range(n):
    for j in range(n):
      row_counts[i][M[i][j]] += 1
      col_counts[j][M[i][j]] += 1

  change_count = 0

  for i in range(n):
    for j in range(n):
      v = M[i][j]
      if row_counts[i][v] > 1 and col_counts[j][v] > 1:
        row_counts[i][v] -= 1
        col_counts[j][v] -= 1
        change_count += 1

  return (change_count
              + get_counts(row_counts)
              + get_counts(col_counts))


num_tests = 1
min_n = 1
max_n = 3

for _ in range(num_tests):
  n = random.randint(min_n, max_n)
  M = [[random.randint(1, 2*n) for j in range(n)]
             for i in range(n)]
  print(M)
  print((brute_force(M), f(M)))