寻找（不太）拉丁方阵中的循环周期

Question

给定一个大小为 m X n 的矩阵，其中行或列中没有重复的值，是否有一种有效的方法来检测循环？例如，这是一个示例矩阵：它至少有一个大小为 3 的置换循环。

3 5 2 9 7 4
4 8 3 1 6 7
1 4 7 5 2 9
9 6 8 2 3 1
2 3 6 7 8 5

第2、4和5行中的3、6和8形成了一个循环。

这个问题与Kakuro拼图有关。与解决它们无关，而是尝试检测特定网格的任何布局是否使其不适用。任何类型的循环都会使该特定布局无效-因为行和列的总和对于两个布局都相同。

- Jim White

---

值3、6和8如何形成一个循环？你能解释得更详细一些吗？我看不出3、6和8之间有任何关系。 - Pham Trung

@PhamTrung：我认为正确的做法是：当您移除第一列、第四列和最后一列以及第一行和第三行时，您将得到一个由数字3、6和8组成的拉丁方阵。 - M Oehm

@MOehm 谢谢，现在我看到了一些联系，如果我们在一行中旋转3、6和8，我们也会得到下一行的下一个排列。 - Pham Trung

是的，M Oehm 完全正确。而且我弄错了行号，这并没有帮助。感谢我的神秘编辑。 - Jim White

我注意到第1行和第3行的2和7也是一个“循环”。 - j_random_hacker

Answer 1

我认为你可以在n x n的网格中用O(n^3)的时间完成此操作。

思路：

考虑你的示例网格，并假设左上角的3和5是否可以出现在拉丁子方阵中。

(3) (5)  2   9   7   4
 4   8   3   1   6   7
 1   4   7   5   2   9
 9   6   8   2   3   1
 2   3   6   7   8   5

因为我们需要一个拉丁方阵，所以我们被迫在（5）列中包含3（每个列中必须出现所有值），并且附近的2也必须包含（必须形成一个方阵）。

(3) (5)  2   9   7   4
 4   8   3   1   6   7
 1   4   7   5   2   9
 9   6   8   2   3   1
(2) (3)  6   7   8   5

我们可以继续运用这种暗示一段时间，但很快就会遇到问题：左侧行没有5。包括左上角的3和左上角的5会导致矛盾。

通常情况下，每当我们在同一行或同一列中包含2个值时，该对将强制包含最多4个其他值，并/或意味着存在矛盾。我们想利用这种暗示结构，快速消除不良解决方案，只留下好的解决方案。

创建一个节点，表示每个水平和垂直值对，并在这些节点之间插入有向边，每当一对暗示另一对必须被包含。还要有一个表示“矛盾”的节点。例如，在示例中，与左上角（3）（5）相对应的{（0,0），（0,1）}对将向{（0,0），（4,0）}、{（0,1），（4,1）}和“矛盾”发出出边。

结果是一个图，有很多节点指向矛盾，并且可能有一些节点在一个循环中相互指向。删除矛盾节点及其直接或间接指向的所有内容，剩下的应该只有循环和任何循环都应该对应于拉丁方阵。

正确性

老实说，我不确定这是否正确。显然，拉丁方阵没有立即被全面检查其正确性，也就是说，每个添加的对都会引起必要的工作...但我认为所有被忽略的坏情况都是那些在输入中保证不会发生值重复的情况。

需要更多的工作。

复杂度

图中有O(n^3)个节点，因为一行或一列中有O(n^2)对，而行+列有O(n)个。边也有O(n^3)，因为每个节点最多有4个出边。

删除指向“矛盾”的东西需要与节点数量成比例的时间，假设您正在使用边缘列表。只需进行反向洪泛填充，沿着上游的入边进行跟踪。

检测循环所需的时间与节点和边的数量成比例：基于它们的出度节点数（最多4个），将节点放入桶中，并删除0出度桶中的节点并重新将受影响的节点放入桶中，直到完成。如果还有剩余节点，则存在循环。

由于所有操作的时间与节点和边的数量成比例，而我们具有O（n ^ 3）个节点+边，因此整个算法需要O（n ^ 3）时间。

- Craig Gidney