Finding cycles in a (not quite) Latin square

Question

Given a matrix of size m X 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 makes it unsuitable. A cycle of any sort would make that particular layout invalid - since the sum of rows and columns is the same for both layouts.

Answer 1

I think you can do this in O(n^3) time, for an n x n grid.

Idea

Consider your example grid, and hypothesize whether the topleft 3 and 5 can end up in a 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 we want a latin square, we're forced to include that 3 in the (5) column (all values must appear in each column), and also the nearby 2 (must form a 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 this implication for awhile, but we'll soon run into a problem: the left row doesn't contain a 5. Including the top-left 3 and the top-left 5 leads to a contradiction.

In general, anytime we include 2 values in the same row or the same column, that pair will force up to 4 other values to be included and/or will imply a contradiction. We want to play with this implication structure to quickly eliminate bad solutions, leaving only good ones.

Make a Graph

Since we have this useful implication structure, we should explore it. Create a node for each horizontal and vertical pair of values, and insert directed edges between those nodes whenever a pair implies another pair must be included. Also have a node for "contradiction". For example, the {(0, 0), (0, 1)} pair corresponding to the top-left (3) (5) in the example would have outgoing edges to {(0, 0), (4, 0)}, {(0, 1), (4, 1)}, and contradiction.

The result is a graph with a lot of nodes pointing at contradiction and, potentially, some nodes pointing at each other in a cycle. Rip out the contradiction node and anything that points to it directly or indirectly, and all that's left should be the cycles and any cycle should correspond to a latin square.

Correctness

I'm honestly not sure if this is correct. It's clear that the latin square is not being immediately exhaustively checked for correctness in the sense of each added pair causing all the necessary work to happen... but I think all the bad cases that would be missed are ones where a value is duplicated and that was guaranteed not to happen in the input.

More work needed.

Complexity

There are O(n^3) nodes in the graph because there are O(n^2) pairs in a row or column, and O(n) rows+columns. There are also O(n^3) edges because each node has at most 4 out-edges.

Removing things pointing at contradiction takes time proportional to the number of nodes, assuming you're using edge lists. Just do a backwards flood-fill, following in-edges upstream.

Detecting a cycle takes time proportional to the number of nodes and edges: bucket nodes based on the number of out-nodes they have (at most 4), and keep removing nodes in the 0-out bucket and re-bucketing the affected nodes until done. If there's anything left, it's a cycle.

Since all operations take time proportional to the number of nodes and edges, and we have O(n^3) nodes+edges, the overall algorithm takes O(n^3) time.