Filling a square grid with non-negative integers with constraints

Question

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.

Answer 1

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