Place Numbers in a Grid Under Row and Column Rules
You must lay numbers 1..k into a k x k grid (each used once, rest zero) subject to 'A must be above B' row rules and 'A must be left of C' column rules. Produce any valid grid or report it is impossible.
Problem
Given k, a list rowConditions where [a,b] means a must appear in a row strictly above b, and colConditions where [a,b] means a must appear in a column strictly left of b, return any k x k matrix placing each of 1..k once (other cells 0) that satisfies all conditions, or an empty matrix if no arrangement exists.
Input
An integer k, rowConditions: list of [above, below], colConditions: list of [left, right].
Output
A k x k matrix satisfying the rules, or an empty list if impossible.
Constraints
- 2 <= k <= 400
- 1 <= rowConditions.length, colConditions.length <= 10^4
- Conditions reference values in 1..k.
Examples
Example 1
Input
k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
Output
[[3,0,0],[0,0,1],[0,2,0]]
Row order 3,1,2 and column order 3,2,1 satisfy every rule (one valid layout).
Example 2
Input
k = 2, rowConditions = [[1,2],[2,1]], colConditions = [[1,2]]
Output
[]
The row rules contradict each other (a cycle), so no layout exists.