algorithm - Finding cycles in a (not quite) Latin square -

given matrix of size m x n no repetition of values in rows or columns, there efficient method of detecting cycles?

for example, here 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 @ least 1 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, , 8 in rows 2, 4 , 5 form cycle.

the problem relates kakuro puzzles. nothing solving them, trying detect whether layout of particular grid makes unsuitable. cycle of sort make particular layout invalid - since sum of rows , columns same both layouts.

i think can in o(n^3) time, n x n grid.

idea

consider example grid, , hypothesize whether topleft 3 , 5 can end in latin sub-square.

(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 

because want latin square, we're forced include 3 in (5) column (all values must appear in each column), , nearby 2 (must form square):

(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 

we can keep doing implication awhile, we'll run problem: left row doesn't contain 5. including top-left 3 , top-left 5 leads contradiction.

in general, anytime include 2 values in same row or same column, pair force 4 other values included and/or imply contradiction. want play implication structure eliminate bad solutions, leaving ones.

make graph

since have useful implication structure, should explore it. create node each horizontal , vertical pair of values, , insert directed edges between nodes whenever pair implies pair must included. have node "contradiction". example, {(0, 0), (0, 1)} pair corresponding top-left (3) (5) in example have outgoing edges {(0, 0), (4, 0)}, {(0, 1), (4, 1)}, , contradiction.

the result graph lot of nodes pointing @ contradiction and, potentially, nodes pointing @ each other in cycle. rip out contradiction node , points directly or indirectly, , that's left should cycles , cycle should correspond latin square.

correctness

i'm not sure if correct. it's clear latin square not being exhaustively checked correctness in sense of each added pair causing necessary work happen... think bad cases missed ones value duplicated , guaranteed not happen in input.

more work needed.

complexity

there o(n^3) nodes in graph because there o(n^2) pairs in row or column, , o(n) rows+columns. there o(n^3) edges because each node has @ 4 out-edges.

removing things pointing @ contradiction takes time proportional number of nodes, assuming you're using edge lists. backwards flood-fill, following in-edges upstream.

detecting cycle takes time proportional number of nodes , edges: bucket nodes based on number of out-nodes have (at 4), , keep removing nodes in 0-out bucket , re-bucketing affected nodes until done. if there's left, it's cycle.

since operations take time proportional number of nodes , edges, , have o(n^3) nodes+edges, overall algorithm takes o(n^3) time.