Hi, I'm here again requesting your help. _(xз」∠)_
This time it is a problem I encountered five years ago, and I still don't know its source.
Here is the problem:
We call a square grid of non-negative integers beautiful if no matter how we pick elements such that there is exactly one element picked in each row and each column, the sum of these elements is always the same.
You are asked to count the number of different $$$n \times n$$$ beautiful grids of non-negative integers, given the values of some places in the grid.
$$$1 \leq n \leq 50$$$, each given value is in $$$[0, 9]$$$ and it is guaranteed that the answer is not infinite.
For example, the number of beautiful grids with the following restriction is $$$24$$$.
0 ? ? ?
? 1 ? ?
? ? 2 ?
? ? ? 3
Tips: It can be reduced to counting the number of integer solutions $$$(x_1, x_2, \ldots, x_n)$$$ such that $$$0 \leq x_i \leq a_i$$$ ($$$a_i \leq 18$$$) for each $$$i$$$, and $$$x_i \leq x_j + w_{i, j}$$$ ($$$0 \leq w_{i, j} \leq 9$$$) for each $$$i, j$$$ ($$$i \neq j$$$).
For all $$$i_{1}, i_{2}, j_{1}, j_{2}$$$ $$$a_{i_{1}j_{1}} + a_{i_{2}j_{2}} = a_{i_{1}j_{2}} + a_{i_{2}j_{1}}$$$, because we can use equal numbers to complete this two pairs to some matching.
For every beautiful grid there exist numbers $$$[x_{1}, x_{2}, \ldots, x_{n}]$$$ (for rows) and $$$[y_{1}, y_{2}, \ldots, y_{n}]$$$ (for columns) such that $$$a_{ij} = x_{i} + y_{j}$$$. From (1) it is easy to see that first column + first row completely determine the grid, and we can take $$$x_{i} = a_{i1}$$$ and $$$y_{j} = a_{1j} - a_{11}$$$.
Let's fix that minimal number in whole grid is $$$c$$$. Subtract $$$c$$$ from all numbers in grid, now minimal number is 0. Let's say that $$$a_{rc} = 0$$$. Then we can take $$$x_{r} = y_{c} = 0$$$ and $$$x_{i} \ge 0, y_{j} \ge 0$$$. This pair of arrays $$$[x_{1}, x_{2}, \ldots, x_{n}]$$$ and $$$[y_{1}, y_{2}, \ldots, y_{n}]$$$ is unique for given grid.
If we have whole row/column of ? then answer is either 0 or inf, because for every correct grid we can do +x on this row/column and get another correct grid.
Let's build a bipartite graph, vertices will be rows and columns, and we have edge if we know $$$a_{ij}$$$. For connected component in this graph if we fix number in one of the vertices, we will know all other numbers. So we can deduce (using dfs) one of two possibilities: given numbers are contradiction or for some fixed vertex there is a range of possible numbers (because all $$$x$$$ and $$$y$$$ should be non-negative), and both endpoints of this range give zeroes for some vertices in one or other part.
For final solution we can try all possibilities of $$$0 \le c \le 9$$$, then find ranges for each component. We have to choose number from each range in such a way that we have zeroes in both parts. It is easy to calculate with linear DP.
Much appreciated! The explanation is very clear!