Debug Exact Cover Pentominoes, Wikipedia example incomplete? OR... I'm misunderstanding something (includes code)

Question

The Problem:

I've implemented Knuth's DLX "dancing links" algorithm for Pentominoes in two completely different ways and am still getting incorrect solutions. The trivial Wikipedia example works OK (https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X#Example), but more complex examples fail.

Debugging the full Pentominoes game requires a table with almost 2,000 entries, so I came up with a greatly reduced puzzle (pictured below) that is still complex enough to show the errant behavior.

Below is my trivial 3x5 Pentominoes example, using only 3 pieces to place. I can work through the algorithm with pen and paper, and sure enough my code is doing exactly what I told it to, but on the very first step, it nukes all of my rows! When I look at the connectedness, the columns certainly do seem to be OK. So clearly I'm misunderstanding something.

The Data Model:

This is the trivial solution I'm trying to get DLX to solve:

Below is the "moves" table, which encodes all the valid moves that the 3 pieces can make. (I filter out moves where a piece would create a hole size not divisible by 5)

• The left column is the encoded move, for example the first row is piece "L", placed at 0,0, then rotated ONE 90-degree turn counter-clockwise.
• vertical bar (|) delimiter
• First 3 columns are the selector bit for which piece I'm referring to. Since "l" is the first piece (of only 3), it has a 1 in the leftmost column.
• The next 15 columns are 1 bit for every spot on a 3x5 pentominoes board.

l_0,0_rr10|100111100001000000
l_0,1_rr10|100011110000100000
l_1,1_rr10|100000000111100001
l_0,0_rr01|100111101000000000
l_0,1_rr01|100011110100000000
l_1,0_rr01|100000001111010000
l_0,0_rr30|100100001111000000
l_1,0_rr30|100000001000011110
l_1,1_rr30|100000000100001111
l_0,1_rr01|100000010111100000
l_1,0_rr01|100000000001011110
l_1,1_rr01|100000000000101111
t_0,1_rr00|010011100010000100
t_0,0_rr10|010100001110010000
t_0,1_rr20|010001000010001110
t_0,2_rr30|010000010011100001
y_1,0_rr00|001000000100011110
y_1,1_rr00|001000000010001111
y_1,0_rr01|001000000100011110
y_1,1_rr01|001000000010001111
y_0,0_rr20|001111100010000000
y_0,1_rr20|001011110001000000
y_0,0_rr01|001111100100000000
y_0,1_rr01|001011110010000000

An Example Failure:

The First Move kills all the rows of my array (disregarding the numeric header row and column)

Following the wikipedia article cited earlier, I do:

• Look for minimum number of bits set in a column
• 4 is the min count, and column 2 is the leftmost column with that bit set
• I choose the first row intersecting with column 2, which is row 13.
• Column 4 and row 13 will be added to the columns and rows to be "covered" (aka deleted)
• Now I look at row 13 and find all intersecting columns: 2, 5, 6, 7, 11 & 16
• Now I look at all the rows that intersect with any 1 in any of those columns - THIS seem to be the problematic step - that criteria selects ALL 24 data rows to remove.
• Since the board is empty, the system thinks it has found a valid solution.

Here's a picture of my pen-and-paper version of the algorithm:

Given the requests for code, I'm now attaching it. The comments at the top explain where to look.

Here's the code:

https://gist.github.com/ttennebkram/8bd27adece6fb3a5cd1bdb4ab9b51166

Second Test

There's a second 3x5 puzzle I thought of, but it hits the same problem the first example has. For the record, the second 3x5 is:

# Tiny Set 2: 3x5
#   u u v v v
#   u p p p v
#   u u p p v

Brachial

Please reduce and enhance this into the expected MRE. Show where the intermediate results deviate from the ones you expect. – Alisander

It's not about the code; the second photograph shows literally the step that's failing. It's the algorithm, not the code, that I'm having trouble with (if it were easy to post the code, I would, but it's mess, and not really the point) – Brachial

If it's about a pure algorithm, why is it tagged with language? That's what threw me off. – Alisander

Ok, so forget the Python tag I guess, my bad. – Brachial

It's unclear to me what exactly is going on in this question. The issue seems to be "The First Move kills all the rows", but I have no idea what that means without any code. – Ploughshare

The paper photo shows the move in question, see the “substep 1”, 2, 3, 4, along with log entries on the paper, using instructions from the Wikipedia article (link above). Sorry if still not clear. I’ll try to see if I can package the code cleanly, but I bet that’ll make it more confusing. – Brachial

Great; your update, the current answer, and the ensuing discussion clarify this well. I retracted the closure vote and reversed the down-vote. I love pentomino puzzles! – Alisander

I've created and added code that demonstrates the problem. – Brachial

@MarkBennett: It looks like you're still having issues with your code. I'm not sure it's a good idea to try to get more answers for your new issues here on this question. My answer below does explain the issue you asked about removing all the rows (it's an error to judge that a success, it should be a failure). If you're having new issues, you really need to ask a new question about them, with details about the failures and perhaps inline code showing where you think things are going wrong. Linking to code is a lot less convenient than seeing it right in front of you. – Ploughshare

Although you brought out an interesting point that I had not considered, it wasn't the root cause of my algorithm's failure. You'll notice that now, even if I follow your logic, I'm still not getting valid solutions. So I really don't think I've moved any goal posts. I was concerned about resubmitting, don't want to get flagged as a duplicate of this one. – Brachial

For the future: note that Wikipedia algorithms are not always good references. In some cases people make changes to the algorithms for various reasons that may or may not work. It doesn't seem to be the case here, but just a warning... – Esteresterase

@HansOlsson thanks. I was starting to wonder if perhaps the Wikipedia worked example is incorrect - NOT incorrect in the specific solution it presents, but some slight misstatement about the rules they followed to arrive at the solution - something that doesn't matter for the small example, but DOES matter for a larger example. As near as I can tell, ALL rows qualify to be deleted in the first iteration or two of the algorithm, with two completely different starting tests. – Brachial

Posted revised code that tries to solve with all 12 pieces, still generating invalid solutions, not sure how to debug with such a giant matrix. Code: gist.github.com/ttennebkram/a16a6a1dc6a1062bb9930f57280f6ae2 – Brachial

Answer 1

Your exact cover implementation seems OK for the reduced instance, but the plotter was broken. I fixed it by changing

boardBitmap = fullBitmap[12:]

to

boardBitmap = fullBitmap[3:]

in plotMoveToBoard_np, since there are only three pieces in the reduced instance.

EDIT: there's also a problem with how you generate move names. There are distinct moves with the same name. There are also duplicate moves (which don't affect correctness but do affect performance). I changed

-                    g_rowNames.append(rowName)
+                    g_rowNames.append(str(hash(str(finalBitmask))))

and 3x20 starts working as it should. (That's not a great way to generate the names, because in theory the hashes could collide, but it's one line.)

Bartley

Wow, looking at this now. So maybe I shouldn't worry that the algorithm seems to nuke rows very aggressively, that maybe that's normal for the algorithm... – Brachial

@MarkBennett I think that's to be expected with pieces that occupy a large fraction of the board. – Bartley

So that certainly fixed the dummy/trivial example I had. But when I enable the full puzzle, it's still generating invalid solutions. :-( I'll post the latest code to a new gist. – Brachial

Revised code posted to gist.github.com/ttennebkram/a16a6a1dc6a1062bb9930f57280f6ae2 – Brachial

Since this was a bug in my code, though doesn't seem to be the root cause, I'll award the points to your answer if I don't get a better answer. But really stumped how to debug this with the full 12 pieces active. – Brachial

@MarkBennett there seems to be a bug in how you generate the move names. See my edit. – Bartley

Wow! And I was looking at new stuff, not the stuff I thought I had nailed a long time ago. Thank you!!!!! (as you can tell, this was really bugging me) – Brachial

For future readers, the final working code, that does the full 6x10, 3x20, etc is now in a new gist: gist.github.com/ttennebkram/357543881836afdd654c40cb4109bca8 – Brachial

Answer 2

The issue you're seeing with your hand-run of the algorithm is that a matrix with no rows is not a solution. You need to eliminate all the columns, just getting rid of the rows is a failure. Your example run still has 12 columns that need to be solved left, so it's not a success.

Ploughshare

I think we’re getting to the core of my issue. I agree, having all rows vanish is bad. But in the Wikipedia example (link above) they talk about covering/deleting all columns and rows at the same time. If you read through their example, on my data, all the rows fall out on the VERY FIRST move, there’s no previous columns to have covered; and with all rows gone, there’s no columns left either. This is the first move in the Wikipedia example (or maybe they have a typo or ambiguity) – Brachial

@MarkBennett This is a backtracking algorithm. So if at first you don't succeed, try, try again. In other words, the row that you picked doesn't lead to a solution, so pick another row. The "look for minimum number of bits set in a column" is an optimization that may lead to a solution faster, but at the end of the day, the algorithm may have to try every possible starting row. – Halfbeak

@MarkBennett In fact, if you look at the shape that row 13 represents, it's a T in the middle of the 3x5 space, so clearly that won't lead to a solution. Rows 14 and 16 are the winners, with 16 matching your desired solution, and 14 leading to the mirror image. – Halfbeak

Agreed with what you said, but according to the Wikipedia example, an empty board indicates a solution. I even posted on StackOverflow to clarify, and folks confirmed: empty = good (it’s recursive, so each time it reduces, and then the stack SHOUKD have the 3 valid moves.) – Brachial

Wikipedia example I’m basing this on: en.m.wikipedia.org/wiki/Knuth%27s_Algorithm_X#Example – Brachial

@MarkBennett You've only deleted (i.e. covered) columns 2,5,6,7,11,16, so even though you've removed all the rows, you still have columns left. – Halfbeak

Read step 1 in the wikipedia article's algorithm up at the top, you'll note it specifically specifies "if the matrix has no columns" you have a solution. Your empty matrix has shape (0, 12) (or (1, 13) with the padding), that's 12 unsolved columns. – Ploughshare

Ok, that could be it... FYI this was my question about terminating the algorithm: #62686715 – Brachial

That suggestion, continuing on with zero rows but still some columns, until there are no more columns, certainly got rid of some of the more spurious false positives, but still produces invalid solutions. I'm really not sure how to package this mess so it's readable by anybody, but looks like I'll need to try. – Brachial

If you have zero rows, you can fail immediately. Really you can fail any time you have a column with zero ones in it (whether that's because there are no rows at all, or because none of them have a 1 in that column). You need to backtrack in those cases and try a different row in a previous step. – Ploughshare

I've created and added code that demonstrates the problem. – Brachial