给定一个大小矩阵，m X n在行或列中没有重复值，是否有一种有效的检测周期的方法？
例如，这是一个示例矩阵：
3 5 2 9 7 4
4 3 6 1 8 7
1 4 7 5 2 9
9 8 3 2 6 1
2 6 8 7 3 5
它至少有一个大小为 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谜题有关。与解决它们无关，而是尝试检测特定网格的任何布局是否使其不适合。任何类型的循环都会使该特定布局无效 - 因为两种布局的行和列的总和是相同的。
我认为对于 nxn 网格，您可以在 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 个其他值和/或暗示矛盾。我们想利用这种暗示结构来快速消除不好的解决方案，只留下好的解决方案。
制作图表
既然我们有这个有用的蕴涵结构，我们应该探索它。为每对水平和垂直的值创建一个节点，并在一对意味着必须包含另一对时在这些节点之间插入有向边。还有一个“矛盾”节点。例如，{(0, 0), (0, 1)}对应于示例中左上角的对将具有到、和(3) (5)的出边。{(0, 0), (4, 0)}{(0, 1), (4, 1)}contradiction
结果是一个图，其中有很多节点指向矛盾，并且可能有一些节点在一个循环中相互指向。撕掉矛盾节点和任何直接或间接指向它的东西，剩下的应该是循环，任何循环都应该对应一个拉丁方格。
正确性
老实说，我不确定这是否正确。很明显，拉丁方并没有立即彻底检查每个添加对的正确性，导致所有必要的工作发生......但我认为所有可能遗漏的坏情况都是重复值和保证不会在输入中发生。
需要做更多的工作。
复杂
图中有 O(n^3) 个节点，因为一行或一列中有 O(n^2) 对，并且 O(n) 行+列。还有 O(n^3) 个边，因为每个节点最多有 4 个出边。
contradiction假设您使用边缘列表，删除指向的东西所花费的时间与节点数成正比。只需在上游边缘进行反向泛洪填充即可。
检测一个循环所花费的时间与节点和边的数量成正比：根据其拥有的 out-node 数量（最多 4 个）对节点进行分桶，并不断删除 0-out 桶中的节点并重新分桶受影响的节点，直到完毕。如果还剩下什么，那就是一个循环。
由于所有操作所花费的时间与节点和边的数量成正比，并且我们有 O(n^3) 个节点+边，因此整个算法需要 O(n^3) 时间。