An efficient algorithm to count the number of integer grids

Question

Consider a square 3 by 3 grid of non-negative integers. For each row i the sum of the integers is set to be r_i. Similarly for each column j the sum of integers in that column is set to be c_j. An instance of the problem is therefore described by 6 non-negative integers.

Is there an efficient algorithm to count how many different assignments of integers to the grid there are given the row and column sum constraints?

Clearly one could enumerate all possible matrices of non-negative integers with values up to sum r_i and check the constraints for each, but that would be insanely slow.

Example

Say the row constraints are 1 2 3 and the column constraints are 3 2 1. The possible integer grids are:

┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│0 0 1│0 0 1│0 0 1│0 1 0│0 1 0│0 1 0│0 1 0│1 0 0│1 0 0│1 0 0│1 0 0│1 0 0│
│0 2 0│1 1 0│2 0 0│0 1 1│1 0 1│1 1 0│2 0 0│0 1 1│0 2 0│1 0 1│1 1 0│2 0 0│
│3 0 0│2 1 0│1 2 0│3 0 0│2 1 0│2 0 1│1 1 1│2 1 0│2 0 1│1 2 0│1 1 1│0 2 1│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

In practice my main interest is when the total sum of the grid will be at most 100 but a more general solution would be very interesting.

Answer 1

Is there an efficient algorithm to count how many different assignments of integers to the grid there are given the row and column sum constraints?

upd My answer is wrong for this particular problem, when N is fixed (i.e. becomes constant 3). In this case it is polynomial. Sorry for misleading information.

TL;DR: I think it's at least NP-hard. There is no polinomial algorithm, but maybe there're some heuristic speedups.

---

For N-by-N grid you have N equations for row sums, N equations for col sums and N^2 non-negative constraints :

For N > 2 this system has more than one possible solution in general. Because there're N^2 unknown variables x_ij and just 2N equations => for N > 2: N^2 > 2N.

You can eliminate 2N - 1 variables to leave with just one equation with K = N^2 - (2N-1) variables getting the sum S. Then you'll have to deal with integer partition problem to find out all possible combinations of K terms to get the S. This problem is NP-complete. And the number of combinations depends not only on the number of terms K, but also on the order of the value S.

This problem reminded me about Simplex method. My first thought was to find just one solution using something like that method and then traverse edges of the convex to find all the possible solutions. And I was hoping that there's an optimal algorithm for that. But no, integer simplex method, which is related to integer linear programming, is NP-hard :(

I hope, there're some kind heuristics for related problems you can use to speedup naive brute force solution.

Answer 2

I don't know of a matching algorithm, but I don't think it would be that difficult to work one out. Given any one solution, you can derive another solution by selecting four corners of a rectangular region of your grid, increasing two diagonal corners by some value and decreasing the other two by that same value. The range for that value will be constrained by the lowest value of each diagonal pair. If you determine the size of all such ranges, you should be able to multiply them together to determine the total possible solutions.

Assuming you described your grid like a familiar spreadsheet alphabetically for columns, and numerically for rows, you could describe all possible regions in the following list:

A1:B2, A1:B3, A1:C2, A1:C3, B1:C2, B1:C3, A2:B3, A2:C3, B2:C3

For each region, we tabulate a range based on the lowest value from each diagonal corner pair. You can incrementally reduce either pair until a member reaches zero because there's no upper bound for the other pair.

Selecting the first solution of your example, we can derive all other possible solutions using this technique.

   A B C
  ┌─────┐
1 │0 0 1│ sum=1
2 │0 2 0│ sum=2
3 │3 0 0│ sum=3
  └─────┘
   3 2 1 = sums

A1:B2 - 1 solution (0,0,0,2)
A1:C2 - 1 solution (0,1,0,0)
A1:B3   1 solution (0,0,3,0)
A1:C3   2 solutions (0,1,3,0), (1,0,2,1)
B1:C2   2 solutions (0,1,2,0), (1,0,1,1)
B1:C3   1 solution (0,1,0,0)
A2:B3   3 solutions (0,2,3,0), (1,1,2,1), (2,0,1,2)
A2:C3   1 solution (0,0,3,0)
B2:C3   1 solution (2,0,0,0)

Multiply all solution counts together and you get 2*2*3=12 solutions.

Answer 3

Maybe a simple 4-nested-loop solution is fast enough, if the total sum is small?

function solve(rowsum, colsum) {
    var count = 0;
    for (var a = 0; a <= rowsum[0] && a <= colsum[0]; a++) {
        for (var b = 0; b <= rowsum[0] - a && b <= colsum[1]; b++) {
            var c = rowsum[0] - a - b;
            for (var d = 0; d <= rowsum[1] && d <= colsum[0] - a; d++) {
                var g = colsum[0] - a - d;
                for (var e = 0; e <= rowsum[1] - d && e <= colsum[1] - b; e++) {
                    var f = rowsum[1] - d - e;
                    var h = colsum[1] - b - e;
                    var i = rowsum[2] - g - h;
                    if (i >= 0 && i == colsum[2] - c - f) ++count;
                }
            }
        }
    }
    return count;
}
document.write(solve([1,2,3],[3,2,1]) + "<br>");
document.write(solve([22,33,44],[30,40,29]) + "<br>");