An Exact Cover problem is commonly denoted as a matrix of 0s and 1s. Columns denote requirements, rows denote possible choices. The problem is solved when a set of rows was found such that, using just this set, each column has exactly one 1 in it. In this question, assume that exactly one solution exists.

A common way to solve such a problem is to pick a column with a lowest number of 1s in it, i.e. few options can fill this requirement. Note that there may be multiple such columns (*). The few rows with a 1 in this column are then systematically tested by iterating over them. Exactly one of them must be correct.

For each tested row, the algorithm recursively selects further rows. If a choice turned out to lead to a dead end (a column cannot be filled anymore), then the algorithms backs up and tries the next option. This is called backtracking.

Suppose I've solved such a problem and know a valid set of rows. I would now like to assist someone else in solving the same problem, also using backtracking. But instead of just telling the solution, I want to tell them which column to start their search in. This refers to case (*), when multiple columns look similarly promising.

The initial column influences the size of the tree that is iterated over. The recursive search process itself has to be repeated, but it is likely shorter. How do I determine which column to give them as a hint?

An exact solution can be calculated by simply enumerating over all permutations of column orders and determining which initial choice has minimum size. However, this is practically infeasible. Is there another way?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.