in reply to decomposing binary matrices
A bipartite graph is a graph where the vertices are partitioned into 2 sets, and every edge crosses between these sets (i.e, does not stay within a set). In this case, one set denotes your variables and the other set denotes your values. Draw an edge between a variable and a value if it is legal to assign that value to that variable.
A matching is a subset of edges from a graph, where no two edges share an endpoint. Since all edges in a bipartite graph run between these 2 sets, you can think of a matching as a (partial) mapping from 1 set to the other (each vertex in set A is paired with at most 1 vertex in set B). In this case, it represents a mapping from variables to values. Since the matching is a subset of the available edges, the mapping doesn't include any assignments that you have deemed "illegal".
What you want is a perfect matching, one that covers all vertices (so it's a 1-to-1 mapping between variables and values). Usually this problem is phrased as the "marriage problem" -- The two sets of vertices are men & women, and there is an edge between a man & a woman if they could be happy married. You want to know if there is a way to pair them up so that each couple is happy (and if there is such a way to pair them up, output it).
An example that I found with pictures is here: bipartite matching. Googling for bipartite matching algorithm turns up plenty of hits. I know that there are efficient algorithms for doing it, but can't remember all of the details.
blokhead