Knuth's Algorithm X for exact cover with restricted block sizes

Question

The famous algorithm for exact cover problem is given by Donald Knuth called Knuth's Algorithm X.

Input: List of subsets of a Universal sets
Output: All the possible disjoint subset whose union is Universal set

Suppose the input is {ab, ac, cd, c, d, a, b}. Is it possible to make the Knuth's Algorithm X such that it will give output according to some predefined block size. For example if {2, 2} is the block size set, it will give output: {ab, cd}, if {2,1,1} is the block size set, it will give output: {ab, c, d}, {ac, b, d} and {cd, b, a}.

Answer 1

You can (optionally) start with removing all subsets from your input list that does not have size in set of block sizes.

The original Knuth's Algorithm X can be altered with the set of block sizes (for example {2, 1, 1}) as a restriction using extensions in bold as follows:

1. If A is empty and set of block sizes is empty, the problem is solved; terminate successfully.
2. Otherwise choose a column, c (deterministically).
3. Choose a row, r, such that A[r, c] = 1 and number of 1s in row r is in the set of block sizes (nondeterministically).
4. Include r in the partial solution
5. Remove number of 1s in row r from set of block sizes
6. For each j such that A[r, j] = 1, Delete column j from matrix A; For each i such that A[i, j] = 1, Delete row i from matrix A.
7. Repeat this algorithm recursively on the reduced matrix A and reduced set of block sizes.