2
$\begingroup$

Knuth's Algorithm X (described here in more details) prescribes that we select a column deterministically (but arbitrary), when we backtrack rows we do not backtrack columns, so we do not have an opportunity, to "rewind", select a different column and try again, during the course of the algorithm.

How can we be sure, that we find all solutions if we do this, and don't miss a few? Or did I get this wrong, and the algorithm cannot actually find every solution? Reading the research paper linked above I got an impression, that it is able to find / enumerate all the solution. So what makes sure we do not miss some of these?

$\endgroup$
2
$\begingroup$

No, it is not necessary to backtrack the columns.

Take an arbitrary solution $X = \{\text{some row indices}\dots\}$. In the first step the algorithm picks some column $j$, and in the second step it iterates over all rows $i$ with $A_{ij} = 1$, makes the matrix smaller and recursively calls itself for each such row.

Since $X$ is a valid solution, there exists some $i_0 \in X$ with $A_{i_0 j} = 1$. Let's analyze the iteration step, in which the algorithm chooses the row $i_0$. How does the matrix change?

  • It removes all columns $k$ with $A_{i_0 k} = 1$: this doesn't bother us. $X / \{i_0\}$ is still a valid solution for the smaller matrix.
  • It removes all rows, that have at least one set $1$ in a same column as row $i_0$: this still doesn't throw away any important stuff. Because we know that all rows in $X$ have the $1$s in different places. So still all rows of the solution will be part of the smaller matrix.

As you see, it doesn't matter how the algorithm picks the column (any choice of column is possible), you will still find a row, that is part of your solution, the solution is still a solution of the smaller matrix. And by induction, we the algorithm will find the solution. Just the order of the rows of the solutions will differ, if we pick some other column. But we will find the same solutions.

$\endgroup$
  • $\begingroup$ How can you demonstrate, that "$X / \{i_0\}$ is still a valid solution for the smaller matrix", when you remove the columns? In general, if you have a matrix $A$ and a solution $X$ and you remove an arbitrary column $c$ from $A$, is $X$ still a solution? $\endgroup$ – Andrew Savinykh Aug 22 '18 at 21:19
  • $\begingroup$ $X / \{i_0\}$ is still a valid solution, because the algorithm removes exactly the columns that have a $1$ in row $i_0$. And because the sets in the solution $X$ form a partition, the remaining sets in $X / \{i_0\}$ form still a partition of the smaller matrix, since you removed exactly the column of $i_0$. You didn't removed a column that is part of a set in $X / \{i_0\}$, and you didn't leave a column that is not part of it. $\endgroup$ – Jakube Aug 23 '18 at 5:32
  • $\begingroup$ E.g. if $\{\{1, 3\}, \{2\}, \{4, 5\}\}$ is a solution, and you currently handle the row corresponding to $\{1, 3\}$, then you remove the columns $1$ and $3$. So $\{\{2\}, \{4, 5\}\}$ is still a partition of the columns $\{2, 4, 5\}$, e.g. is still a solution of the smaller matrix. @AndrewSavinykh $\endgroup$ – Jakube Aug 23 '18 at 5:32
  • $\begingroup$ You mention a partition. Is this a partition of $X$, a partition of $A$, a partition of all rows/columns in $A$ or something else? It's not very clear to me. $\endgroup$ – Andrew Savinykh Aug 23 '18 at 6:09
  • $\begingroup$ @AndrewSavinykh In the exact cover problem you want to find a partition of a set. In the algorithm X, this corresponds to a partition of the columns. $\endgroup$ – Jakube Aug 23 '18 at 7:42
2
$\begingroup$

We need to ensure that, in each column, we have chosen at least one entry (one row) that contains a 1. It doesn't matter what order we consider the columns in; any such order will give us a valid solution.

For example, suppose we first choose a row for column 1; then we choose a row for column 2. That will explore all possible solution. Alternatively, you could first choose a row for column 2, then choose a row for column 1; but that will give the same set of solutions, just in a different order (because a solution describes which row you chose for column 1 and which row you chose for column 2).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.