Dynamic Programming Question, selecting 1s in a 0-1 matrix such that each row and column contain exactly one 1

Given a 0-1 square matrix, In how many ways can we select 1's such that each row and column contain exactly one 1??

I've implemented the following backtrack code for this problem:

    int countways(int A[][], int& n, int row, vector<bool> columnselected ) {
         if(row == n)
              return 1;
         int result = 0;
         for( j = 0; j < n ; ++j) {
              if(A[row][j]) {
                   if(!columnselected[j]) {
                        columnselected[j] = true;
         开发者_如何学编程               result+ = countways(A, n, row+1, columnselected);
                        columnselected[j] = false;
                   }
               }
         }
         return result;
     }

This is definitely not the best way to solve this problem. I can't enhance the solution by using a memoized version of the recursion since columnselected and row in every call to the recursion would be unique for every sub-problem.

Please suggest a better approach to solve this problem, more like a dynamic programming solution, more efficient than this obvious solution.

This problem is equivalent to finding the number of perfect matchings for a bipartite graph. Take the NxN matrix, and create a vertex for each row and a vertex for each column (2N vertices). Add an edge between a row vertex and column vertex iff the matrix contains a '1' in the corresponding row and column. This forms the bipartite graph. Note that finding a perfect matching in this graph is equivalent to selecting "1's such that each row and column contain exactly one 1".

From Wikipedia:

The problem of determining the number of perfect matchings in a given graph is #P Complete (see Permanent). However, a remarkable theorem of Kasteleyn states that the number of perfect matchings in a planar graph can be computed exactly in polynomial time via the FKT algorithm. Also, for bipartite graphs, the problem can be approximately solved in polynomial time.[8] That is, for any ε>0, there is a probabilistic polynomial time algorithm that determines, with high probability, the number of perfect matchings M within an error of at most εM.

Note: You can determine if the answer is zero or not in polynomial time.

So, a perfect polynomial time solution isn't possible, but we can improve the asymptotic runtime of your function (from O(N*N!) to O(N*2^N)) with memoization. Only the "columnselected" variable needs to be "memo"ed. (Changing "columnselected" to be a bitmasked integer instead of vector should also improve performance and have a simpler implementation).

I am afraid that your best bet is to modify Knuth's Algorithm X, explained in more detail in http://en.wikipedia.org/wiki/Exact_cover. The key is to use a similar data structure as is used in Algorithm X.

I am pretty sure the problem you described is equivalent to exact cover, which makes it NP-complete. Therefore no "efficient" solution is available, but algorithm X will be okay in practice.

If I understand your question correctly, isn't this problem same as awarding unique ranks to each column? For example, if there is a 1 at [p,q], it means the q'th column is allotted a rank p.

So for a NxN matrix, the solution should be N! (factorial of N)

You can also use induction P(N) = n * P(N-1), since when you place a 1 anywhere in a NxN matrix, a row and column are blocked by it - so you are left with a (N-1)x(N-1) matrix.

EDIT: My understanding of the problem was incorrect. But here is a fresh attempt with dynamic programming approach

Let's create a DAG first like thus: The nodes of this graph are squares Square(p,q,size) - square anchored at row=p,col=q with size x size elements. Yes, they can wrap around. For computational simplicity, lets have q always equal to 0.

For the matrix {{abc},{def},{ghi}}, the nodes will be

{a}, {d}, {g} : squares with size 1 : root nodes

{ab,de} , {de, gh}, {gh, ab} : squares of size 2

{{abc},{def},{ghi}} : only square of size N i.e. matrix itself : leaf node

Directed Edges point from squares of size n to n+1 AND if the small square can be contained in the bigger one. For example {d} points to both {ab,de} and {de, gh} Important: There cannot be any edge between size n and size n+2 squares

Traversal

Base: Assign weights to size 1 squares: Square (p,0,1) = 1 iff M(p,0)==1

Step: For squares of size N, visit it's children i.e. squares of size N+1. Contribute own weight to child if the corner it is growing to is 1, else don't.

The leaf node would have your answer.

This solution is basically a bottom up approach of your traversal and it will avoid duplicate calculations of sub-problems.