How can I properly understand the 'exact cover' algorithm?

Question

0.00/5 (No votes)

See more:

I'm trying to implement Knuth's 'Algorithm X' to solve exact-cover matrix problems, and have come across a simple matrix which causes the algorithm to fail. Either that, or I haven't understood the description of the algorithm! I strongly suspect the latter, so would be most grateful for someone pointing out where I've gone wrong.

I used the post in this forum titled "Solve the Pentomino puzzle with C++ and dancing links" for the scheme of labeling the matrix, and for the description of the algorithm. See the section "Algorithm X". AFAICS, the algorithm given there is exactly as described elsewhere, e.g. Wikipedia at Knuth's Algorithm X , and in Knuth's own paper 'Dancing Links'.

The algorithm as I understand it:

1. Find the column with fewest 1s.
2. For that column, choose a row where that column has a 1.
3. For that row, choose the columns where the value in the row is 1, and for each of those columns, remove all rows where the value in the column is 1.
4. Remove the columns selected in step 3.

The test matrix I used is this:

C++

My interpretation of this, for my example matrix, is:

1. Column with fewest 1s: { A }.
2. Row with 1 in column A: { R }.
3. Columns having a 1 in row R: { A, C }
   Remove rows having a 1 in column A: { R, S }
   Remove rows having a 1 in column C: { P, Q }
4. Remove columns { A, C }

Step 4 is redundant as the matrix is already empty by then.

This leaves an empty matrix, which is the signal that a solution has been found, consisting of the row in the partial solution, i.e. row R. However, row R by itself is NOT a solution, as it has no 1 in column B. In fact there is no solution containing R; the only valid solution contains rows P and S.

What I have tried:

I've tried reading many different descriptions of 'Algorithm X', and all suggest that I'm doing it the way it should be done. Could there be cases where the algorithm fails, or have I just misunderstood?

Please tell me where my understanding of the algorithm has broken down! :)

Posted 7-Jan-21 14:00pm

old_hacker

Updated 9-Jan-21 12:43pm

v2

Add a Solution

Comments

[no name] 8-Jan-21 2:19am

You said A "AND" C; then go on to delete any A "OR" C. Which is it? AND or OR? Or none of the above?

old_hacker 8-Jan-21 17:29pm

Thanks for responding; however, I don't understand your question. I've edited my original post, trying to clarify the relevant part.

old_hacker 9-Jan-21 4:37am

It occurred to me, after noticing that Wikipedia's version of the algorithm says "If the matrix has no columns...", that a column may be viewed as still existing even though it has no rows. My implementation of the matrix was as a vector of rows, which seemed most natural, so empty columns could not be represented. I'll recode it as a vector of columns and try again.

[no name] 9-Jan-21 10:18am

You said: "1. pick the column with the fewest ones" ... and you picked "A".

Columns A and B have the same number of 1's ... how can you claim "A" has the "fewest"?

old_hacker 9-Jan-21 17:44pm

First among equals! :)
Discussion elsewhere indicates that the first of the fewest is the one to use.

Anyway, my conjecture about a matrix with columns of zero rows being considered non-empty proved to be correct. See my solution below.

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

old_hacker · Answer 1 · 2021-01-09T12:43:00

The algorithm as stated in the post I quoted is not quite right. The test for 'empty matrix' must be 'matrix has zero columns', where columns that have not been deleted are still 'present' even though all rows have been deleted.

The algorithm as described works when used in the 'dancing links' program, because the matrix data structure has column headers; they are not deleted just because all the rows have been, so they stay and provide a non-empty matrix until all columns are deleted.

For 'normal, mathematical' matrices, which can't have zero rows, a simple fix is to add a row of all zero bits. This is sort of equivalent to the column headers mentioned above. That row will never be selected, because it has no 1 in any column, and will never be deleted, for the same reason. Thus the matrix will never be empty until all columns have been deleted. If the row of zeroes is the only row left, the algorithm terminates with failure. This 'dodge' means that a pencil-and-paper solving will work.