If I have understood the problem correctly, any time N variables can only be the same N values, they can be extracted from the matrix. This process is repeated until you are left with a "left over" matrix. Presumably this reduces the amount of brute force necessary to find values.

This also sounds like a job best solved by Prolog or some other logic programming language as we are trying to searching to satisfy constraints.