Given a matrix of size $m \times n$ with no repetition of values in rows or columns, is there an efficient method of detecting cycles?
For example, here is a sample matrix:
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
It has at least one permutation cycle of size 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
The values 3, 6, and 8 in rows 2, 4 and 5 form a cycle.
The problem relates to Kakuro puzzles. Nothing to do with solving them, but trying to detect whether any layout of a particular grid (of overlapping matrices) makes it unsuitable. A cycle of any length within any sub-block would make that particular layout undesirable - since the sum of rows and columns is the same in each case, so the puzzle is ambiguous.
The matrices are not strictly Latin - the number of symbols exceeds the rank. With just 9 symbols, the problem can be practically solved by exhaustive search. But what if my symbol set (allowed values) was larger, and the matrix correspondingly bigger?
My exhaustive search algorithm is:
For a given cycle length $p$ and
candidate tl-corner position ($r$, $c$), I take all combinations of
rows and columns that could form a $p \times p$ sub-matrix with that corner.
There are $k = C(n-r, p-1)$ possibilities for both row and column, for a total of $k^2$
candidate-sets.
For each set I count the number of different values, $d$ in that set. If $d = p$ then it must be a cycle.