1
$\begingroup$

Let us suppose you have an n by n grid, and for each row and column, you are given n numbers you need to place in that row.

Is it known if there are any not very restrictive conditions you can put on the contents of the rows and columns that will be sufficient to ensure you can put a number in each cell, so as to get the correct contents for each row and column?

Clearly necessary conditions include:

  • Every item appears the same number of times in the rows and the columns
  • Each row must intersect each column

As an example: for n=3, if you are told row 1 must contain {1,2,4}, row 2 must contain {1,3,5} and row 3 must contain {2,3,6}, but column 1 must contain {1,3,4}, column 2 must contain {2,3,5} and column 3 must contain {1,2,6}:

  • In row 1, the 4 must clearly go in column 1, and then the 1 must go in column 3 (since there is no 1 in column 2)
  • In column 3, neither the 6 or 2 appear in row 2, so we are stuck.
$\endgroup$
0
$\begingroup$

There cannot be easy-to-check necessary and sufficient conditions, because this problem is NP-complete.

(I guess you might impose sufficient conditions for the grid to be able to be completed that are not necessary conditions: for example, it's trivial to fill in the grid if no number is repeated in two rows or two columns.)

To show this, we will appeal to a known NP-complete problem: Latin square completion. This is a very similar problem to this one. A Latin square is an $n \times n$ grid filled with the numbers $1$ through $n$ such that every number appears exactly once in every row and exactly once in every column. In the Latin square completion problem, you are given a partial grid such as the one below: $$\begin{bmatrix} 1 & & \\ & 3 & 1 \\ & & 2 \end{bmatrix}$$ and asked if we can complete it to a Latin square by filling in the empty cells.

To encode this as an instance of the row-column problem you define here, first write down the remaining numbers that we need in each row and column. In this $3\times 3$ example, that's $\{2,3\}$ for row $1$, $\{2\}$ for row $2$, $\{1,3\}$ for row $3$, $\{2,3\}$ for column $1$, $\{1,2\}$ for column $2$, and $\{3\}$ for column $3$.

The other thing we need to make sure is that none of these values are put in the places where the Latin square is already filled in. So replace all those places by unique values: $$\begin{bmatrix}101 & & \\ & 202 & 203 \\ & & 303\end{bmatrix}$$ and ensure that those values must be placed there by adding that value only to the row and the column where it occurs.

So we get the final set of constraints that row $1$ must have $\{2,3,101\}$, row $2$ must have $\{2,202,203\}$, row $3$ must have $\{1,3,303\}$, column $1$ must have $\{101,2,3\}$, column $2$ must have $\{1,2,202\}$, and column $3$ must have $\{3, 203,303\}$.

So if you find a quick way to check if a grid with such constraints can be filled, you can use it to quickly check if a Latin square can be completed, and then you can claim your million dollars for proving that P=NP.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.