What is the most efficient algorithm for solving the cell-sum puzzle?

Question

The cell-sum puzzle is defined as follows:

Given two sets of non-negative integers X = {x₁, x₂,...,x_m} and Y = {y₁, y₂,...,y_n}, fill each cell in a grid of m rows and n columns with a single non-negative integer such that x_i is the sum of the cells in the ith row for every i ≤ m and such that y_j is the sum of the cells in the jth column for every j ≤ n.

For example, if X = {7, 13} and Y = {8, 9, 3}, then your goal would be to replace the question marks in the following grid:

? + ? + ? = 7
+   +   +
? + ? + ? = 13
=   =   =
8   9   3

and a valid solution would be:

3 + 1 + 3 = 7
+   +   +
5 + 8 + 0 = 13
=   =   =
8   9   3

How do you solve this puzzle for arbitrarily large m and n? Also, for your method of choice, do you know the time complexity, and can you tell whether it is the most efficient algorithm possible?

Answer 1

Here's a linear-time algorithm (O(m + n) assuming we can output a sparse matrix, which is asymptotically optimal because we have to read the whole input; otherwise O(m n), which is optimal because we have to write the whole output).

Fill in the upper-left question mark with the min of the first row sum and the first column sum. If the first row sum equals the min, put zeros in the rest of the row. If the first column sum equals the min, put zeros in the rest of the column. Extract the subproblem by subtracting the new value from the first row/column if they remain and recurse.

On your example:

? + ? + ? = 7
+   +   +
? + ? + ? = 13
=   =   =
8   9   3

Min of 7 and 8 is 7.

7 + 0 + 0 = 7
+   +   +
? + ? + ? = 13
=   =   =
8   9   3

Extract the subproblem.

? + ? + ? = 13
=   =   =
1   9   3

Min of 13 and 1 is 1.

1 + ? + ? = 13
=   =   =
1   9   3

Extract the subproblem.

? + ? = 12
=   =
9   3

Keep going until we get the final solution.

7 + 0 + 0 = 7
+   +   +
1 + 9 + 3 = 13
=   =   =
8   9   3