k and two lists of rules. A rule [a, b] in row_rules means number a must be in a row strictly above number b. A rule [a, b] in col_rules means a must be in a column strictly to the left of b. All numbers in the rules are between 1 and k.
Build a k × k grid that contains every number from 1 to k exactly once, has 0 in all other cells, and satisfies every rule.
To make the answer unique, rows are handed out like this:
1. First, every number that never appears as b in any rule joins a queue, in ascending order.
2. While the queue is not empty, take the number at its front and give it the next free row from the top (0, 1, 2, ...).
3. Then go through the row_rules that have this number as a, in the order they are listed, crossing each one out. As soon as a number b has no uncrossed rules left where it is b, it joins the back of the queue.
Columns are handed out the same way from col_rules. If not all k numbers get a row, or not all get a column, the rules contradict each other: return an empty list.k=3, row_rules=[[2, 1], [3, 1]], col_rules=[[1, 3], [3, 2]] → [[0, 0, 2], [0, 3, 0], [1, 0, 0]]
Rows: 2 and 3 start free and get rows 0 and 1, then 1 gets row 2. Columns: only 1 starts free (column 0), then 3 (column 1), then 2 (column 2).
k=2, row_rules=[[1, 2]], col_rules=[[1, 2], [2, 1]] → []
In columns 1 must be left of 2 and 2 left of 1, which is a contradiction, so the answer is empty.
k=4, row_rules=[[4, 2], [4, 1]], col_rules=[[3, 1]] → [[0, 3, 0, 0], [0, 0, 4, 0], [2, 0, 0, 0], [0, 0, 0, 1]]
k ≤ 400len(row_rules), len(col_rules) ≤ 10⁴a, b ≤ k, a ≠ bk=3, row_rules=[[2, 1], [3, 1]], col_rules=[[1, 3], [3, 2]]
[[0, 0, 2], [0, 3, 0], [1, 0, 0]]
Run checks the first 3 tests in your browser. Submit checks all 86 tests on the server, hidden ones included.