# Filling a square grid with non-negative integers with constraints

This question can be considered as a generalization of this question (which was not answered).

Set-up

Consider we have a square grid of $$N_x \times N_y$$ sites with a non-negative integer $$S_{ij}$$ on each site $$(i,j)$$, $$i=1,\dots,N_x$$; $$j=1,\dots,N_y$$. The total sum of all $$S_{ij}$$ is $$M$$, and sums of $$S_{ij}$$ in each column and each row are $$X_1, \dots, X_{N_x}$$ and $$Y_1, \dots, Y_{N_y}$$ correspondingly. There is also an additional constraint on the maximum value of $$S_{ij}$$ at each site: $$S_{ij} \leq S_\text{max}$$ for $$\forall i, j$$.

Questions

Suppose we are given a set of non-negative integer numbers $$\lbrace M, X_1, \dots, X_{N_x}, Y_1, \dots, Y_{N_y}, S_\text{max} \rbrace$$, which determine the constraints above. The questions I am interested in are:

1. Is there a way to determine whether there exists a configuration $$\lbrace S_{ij} \rbrace$$ which satisfies given constraints?
2. How many different configurations $$\lbrace S_{ij} \rbrace$$ satisfy given constraints?
3. Is there any efficient algorithm to construct some configuration $$\lbrace S_{ij} \rbrace$$ which satisfies given constraints? (by efficient I mean something better than brute-force search)
4. Is there any efficient algorithm to construct all configurations $$\lbrace S_{ij} \rbrace$$ which satisfy given constraints?

My thoughts

1) Of course the total sum of $$S_{ij}$$ should be the same: $$M = \sum_{i=1}^{N_x} X_i = \sum_{j=1}^{N_y} Y_j$$. Also, it is obvious that $$M \leq N_x N_y S_\text{max}$$, $$X_i \leq N_y S_\text{max}$$ for any $$i$$, $$Y_j \leq N_x S_\text{max}$$ for any $$j$$. If the given set of numbers doesn't fulfil these conditions, the configuration doesn't exist. In case $$S_\text{max} \rightarrow \infty$$ these conditions seem to be enough for a valid configuration to exist (however, I'm not sure; I would be happy if someone could confirm and prove this). But in case $$S_\text{max}$$ is finite these conditions are definitely not enough (A simple counterexample: $$N_x=N_y=2$$, $$S_\text{max}=10$$, $$M = 25$$, $$X_1=20$$, $$X_2=5$$, $$Y_1=7$$, $$Y_2=18$$). This thought led me to another type of conditions which have to be satisfied: $$X_i - (N_y - 1)S_\text{max} \leq Y_j$$ and $$Y_j - (N_x - 1)S_\text{max} \leq X_i$$ for $$\forall i,j$$. However, I still don't know if this is enough.

3) If a valid configuration exists, my proposition for the algorithm is the following: fill up the sites starting from the corner (1,1) and first going over the first row, then over the first column: (1,1)->(2,1)->(3,1)->...->($$N_x$$,1)->(1,2)->(1,3)->...->(1,$$N_y$$). Then starting from (2,2) go over the leftovers of the second row and the second column. And so on. Fill each site with $$S_{ij} = \min \left( X_i - \sum_{j' < j} S_{ij'}, \enspace Y_j - \sum_{i' < i} S_{i'j}, \enspace S_\text{max} \right)$$. I am not sure if this approach will always result in a valid configuration though.

I will be happy to see your thoughts on any of these.

You can determine existence by solving an integer linear programming problem with $$S_{i,j}\in[0,S_\max]$$ as the integer variables and two sets of linear constraints: \begin{align} \sum_j S_{i,j} &= X_i &&\text{for all i}\\ \sum_i S_{i,j} &= Y_j &&\text{for all j} \end{align} Some solvers will optionally find all feasible solutions.
For the special case of $$S_\max=1$$, there is a majorization criterion to check existence. See Brualdi, Algorithms for constructing (0, 1)-matrices with prescribed row and column sum vectors (2006).