I was wondering if the following problem has been studied/has a name:
Given a matrix of numbers (may assume to be integers), find the smallest number of rules which define the matrix. Three kinds of rules may be used:
- row rules: row[i, x] - the value of any cell in row i is x
- column rules: col[j, x] - the value of any cell in column j is x
- cell rules: cell[i, j, x] - the value of cell at [i,j] is x
The rules have a precedence order: first cell rules are considered, then row rules, then column rules.
Given the 3 x 3 matrix:
2 2 2 1 2 3 1 3 3
one set of rules which describe the matrix is:
row[1,2], col[3,3], col[1,1], cell[2,2,2], cell[3,2,3]
Edit: I would be interested in getting opinions on what the complexity is of this problem. I have a polynomial time algorithm which does well enough for my use cases, but it would nice to know if the general case is not in P.