Search for loops in (not really) Latin square

Question

Given a matrix of size m X n without repeating the values ​​in rows or columns, is there an efficient loop detection method?

For example, here is an example 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 size 3 permutation loop:

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 lines 2, 4, and 5 form a loop.

The problem is with Kakuro puzzles. Nothing has to do with their decision, but is trying to determine if any layout of a particular mesh is not suitable. A loop of any type will invalidate this particular layout — since the sum of the rows and columns is the same for both layouts.

Answer 1

I think you can do it O (n ^ 3) times, for an nxn grid.

Idea

Consider your grid example and suggest if topleft 3 and 5 can end up in the 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 

Since we need a Latin square, we are forced to include this 3 in column (5) (all values ​​should appear in each column), as well as nearby 2 (should 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 continue to do this implication for a while, but we will soon encounter a problem: the left line does not contain 5. Including the upper left 3 and the upper left 5 leads to a contradiction.

In general, at any time we include 2 values ​​in the same row or the same column, this pair will cause up to 4 other values ​​to be included, and / or will mean a contradiction. We want to play with this implication structure to quickly eliminate bad decisions, leaving only good ones.

Make a schedule

Since we have this useful structure of implication, we must study it. Create a node for each horizontal and vertical pair of values ​​and insert directional edges between these nodes whenever the pair implies that another pair should be included. There is also a node for the "contradiction." For example, the pair {(0, 0), (0, 1)} corresponding to the upper left (3) (5) in the example would have outgoing edges on {(0, 0), (4, 0)} , {(0, 1), (4, 1)} and contradiction .

The result is a graph with many nodes indicating a contradiction, and potentially some nodes pointing to each other in a loop. Tear out the contradiction node and everything that points to it directly or indirectly, and everything that remains, should be a cycle, and any cycle should correspond to the Latin square.

Correctness

I'm honestly not sure if this is correct. It is clear that the Latin square is not directly tested for correctness in the sense of each added pair, causing all the necessary work to happen ... but I think that all the bad cases that will be missed are those where the value is duplicated and that is guaranteed not to happen at the entrance.

It takes more work.

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) are rows + columns. There are also O (n ^ 3) edges, because each node has at most 4 outer edges.

Removing objects that indicate contradiction takes time proportional to the number of nodes, provided that you use edge lists. Just backfill, following the edges upstream.

Loop detection takes time proportional to the number of nodes and edges: bucket nodes based on the number of remote nodes that they have (no more than 4) and continue to delete nodes in the 0-out bucket and re-align until they are completed . If something remains, this is a cycle.

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