in reply to decomposing binary matrices

This may be completely off target but the problem reminds me of the mental gymnastics used when solving Sudoku puzzles. I saw a Perl Sudoku solver once and the author had employed the Quantum::Superpositions module and it's any and all functions. Just a thought but perhaps something in there could help you.