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

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.)

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.