algorithm - 一种计算整数网格个数的高效算法

Question

考虑一个由非负整数组成的 3 x 3 正方形网格。对于每一行 i，整数之和设置为 r_i。类似地，对于每一列 j，该列中的整数总和设置为 c_j。因此，问题的实例由 6 非负整数描述。

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?

很明显，可以枚举所有可能的非负整数矩阵，其值最大为 sum r_i 并检查每个矩阵的约束，但这会非常慢。

示例

假设行约束是 1 2 3，列约束是 3 2 1。可能的整数网格是:

┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│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│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

在实践中，我的主要兴趣是网格的总和最多为 100，但更通用的解决方案会非常有趣。

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 当 N 固定时(即变为常量 3)，我对这个特定问题的回答是错误的。在这种情况下，它是多项式的。对于误导性信息，我们深表歉意。

TL;DR:我认为它至少是 NP 难的。没有多项式算法，但也许有一些启发式加速。

---

对于 N×N 网格，您有 N 行总和方程，N 列总和方程和 N^2 非负约束:

对于 N > 2，这个系统通常有不止一种可能的解决方案。因为有 N^2 个未知变量 x_ij 和只有 2N 个方程 => 对于 N > 2:N^2 > 2N。

您可以消除 2N - 1 变量，只剩下一个方程，其中 K = N^2 - (2N-1) 变量得到总和 S 。那么你将不得不处理 integer partition problem找出 K 项的所有可能组合以获得 S。这个问题是 NP 完全的。并且组合的数量不仅取决于项K的数量，还取决于值S的顺序。

这个问题让我想起了Simplex method .我的第一个想法是使用类似该方法的方法只找到一个解决方案，然后遍历凸面的边缘以找到所有可能的解决方案。我希望有一个最佳算法。但不是，整数单纯形法，与integer linear programming有关, 是 NP-hard :(

我希望，您可以使用一些针对相关问题的启发式方法来加速简单的暴力解决方案。