# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Find row subsets of an input binary matrix that sum to 1 in each column

Contributed by:
Bradley Klee

ResourceFunction["FindExactCover"][ finds a row subset of the binary matrix | |

ResourceFunction["FindExactCover"][ finds all row subsets with sum equal to 1 in each column. | |

ResourceFunction["FindExactCover"][ finds up to |

An *exact cover* is a partitioning of a set of elements into disjoint subsets whose union is exactly the original set.

The exact cover (XC) problem gives an original set along with a list of allowable subsets and asks if any selection of the allowable subsets is an exact cover of the original set. It is an NP complete problem, and very similar to graph clique finding (cf. FindClique).

Here we do not deal with sets and subsets, but rather with binary matrices. The input binary matrix *mat* lists allowable subsets as rows and set elements as columns, by coding that the k^{th}element of the original set is also a member of the j^{th} listed subset if and only if *mat*_{jk}=1. Thus a one's row {1,1,…,1} represents a trivial exact cover.

Sometimes the terms *items *and *options *are used in place of column and row headers respectively. The exact cover problem can then be stated as follows: Choose a set of options such that every item is included in exactly one option.

If two options are not disjoint, their respective row sum will have a value exceeding 1 in at least one column. Similarly, if neither of two options includes the k^{th} item, their respective row sum will have a 0 in the k^{th} column. Let { j_{1},j_{2},… }∈𝒪 be a set of options. It is an exact cover if and only if the respective row sum satisfies that .

Now define a graph whose vertices are options and whose edges indicate pairwise disjunction. Cliques in the graph represent maximal sets of disjoint options, which can easily be tested for the exact cover property once they are found.

FindExactCover has a Method option for switching between three distinct algorithms:

"DancingLinksX" | Donald Knuth's algorithm |

"CliqueToCover" | transforms input to a graph and uses FindClique |

"BranchAndPrune" | uses a depth-first search |

When using the DancingLinksX method, setting the Heuristic sub-option to either Automatic or "Increment" changes the search order:

{"DancingLinksX","Heuristic"→ Automatic} | Knuth's suggested MRV heuristic |

{"DancingLinksX","Heuristic"→ "Increment"} | select right-nearest column |

The "MRV heuristic" chooses to cover the next item with the minimal number of associated options.

ResourceFunction["FindExactCover"] ignores empty subsets, i.e. zero's rows of the form {0,0,…,0}.

An IdentityMatrix has only one exact cover:

In[1]:= |

Out[1]= |

List the five set partitions of three objects into disjoint sets:

In[2]:= |

Out[2]= |

Solve an example problem from Wikipedia:

In[3]:= |

Out[3]= |

Find an exact cover of the columns of a 5×4 matrix:

In[4]:= |

Out[4]= |

Test the row sum property:

In[5]:= |

Out[5]= |

Find all exact covers:

In[6]:= |

Out[6]= |

Ask for only five results:

In[7]:= |

Out[7]= |

For small simple inputs, setting the "Heuristic" suboption to "Increment" can get results faster:

In[8]:= |

Out[8]= |

The Automatic heuristic can go noticeably faster for more complex inputs:

In[9]:= |

Out[9]= |

But alternative methods can still be faster for relatively small, unstructured inputs:

In[10]:= |

Out[10]= |

The default Dancing Links X method should be relatively slow when every valid choice leads to another result:

In[11]:= |

Out[11]= |

Dancing Links X may also be slower in the limit of small inputs:

In[12]:= |

Out[12]= |

But Dancing Links X can have better complexity scaling:

In[13]:= |

Out[13]= |

Find a solution to Scott's pentomino problem:

In[14]:= |

Out[14]= |

Count number of length-n set partitions by enumerating them (cf. OEIS A000110):

In[15]:= |

Out[15]= |

Compute the first few terms of the Tetris sequence (cf. OEIS A174248):

In[16]:= |

Out[16]= |

Compute the first few terms of the N Queens sequence (cf. OEIS A000170):

In[17]:= |

Out[17]= |

- 1.0.0 – 18 November 2022

This work is licensed under a Creative Commons Attribution 4.0 International License