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}
.
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:
A
is empty and set of block sizes is empty, the problem is solved; terminate successfully.c
(deterministically).r
, such that A[r, c] = 1
and number of 1s in row r
is in the set of block sizes (nondeterministically).r
in the partial solutionr
from set of block sizesj
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
.A
and reduced set of block sizes.