Algorithm X With Overlapping Tiles

Knuth’s Algorithm X details a method to solve exact cover problems, but it cannot handle overlapping tiles.

A demo of a modified Algorithm X which handles overlapping pieces can be found at https://acarlson99.github.io/static/dlx/ with its implementation here https://github.com/acarlson99/acarlson99.github.io/tree/master/static/dlx

This is especially useful for extending AlgoX to operate on words which frequently have duplicate letters.

Original Algorithm X

From https://en.wikipedia.org/wiki/Knuth’s_Algorithm_X#Example

1. If the matrix A has no columns, the current partial solution is a valid solution; terminate successfully.
2. Otherwise choose a column c (deterministically).
3. Choose a row r such that A_r,c = 1 (nondeterministically).
4. Include row r in the partial solution.
5. For each column j such that A_r,j = 1,
   1. for each row i such that A_i,j = 1
      1. delete row i from matrix A.
   2. delete column j from matrix A.
6. Repeat this algorithm recursively on the reduced matrix A.

A classic Algorithm X example

A detailed breakdown of solving this matrix can be found by the curious at https://en.wikipedia.org/wiki/Knuth’s_Algorithm_X#Example

However, this only solves an exact cover. If we want 2 tiles to occupy COL 7 this cannot be solved by base Algorithm X.

This can be solved by introducing a count representing the number of tiles we want to cover each column. Additionally, with this change the algorithm can be expanded to handle numbers > 1.

Modified version

New algorithm description with Counts

1. If the matrix A has no columns, and Counts all no non-zero values the current partial solution is a valid solution; terminate successfully.
2. Otherwise choose a column c (deterministically).
3. Choose a row r such that A_r,c ≥ 1 (nondeterministically).
4. Include row r in the partial solution.
5. For each column j such that A_r,j ≥ 1,
   1. Reduce Counts_j by A_r,j.
   2. for each row i such that A_i,j > Counts_j
      1. delete row i from matrix A.
   3. delete column j from matrix A.
6. Repeat this algorithm recursively on the reduced matrix A.

Example

Consider this example where we want to cover column 7 twice Counts = { 1:1, 2:1, 3:1, 4:1, 5:1, 6:1, 7:2 }

Level 0

Step 1 - Non-empty matrix, we proceed.

Step 2 - Choose the column with the fewest 1s and is selected deterministically

Step 3 - Rows A and B each have a 1 in column 1 and are selected nondeterministically

Level 1: Select Row A

Step 4 - Row A is included in the partial solution

Step 5 - Row A has 1 in columns 1, 4, and 7

Column 1 has a 1 in rows A and B; column 4 has a 1 in rows A, B, and C; and column 7 has a 1 in rows A, C, E, and F. [1,4,7].map(a => Counts[a] -= 1) results in Counts[1] = 0; Counts[4] = 0; Counts[7] = 1;

Thus, rows A, B, and C are to be removed and columns 1 and 4 are to be removed:

The matrix now looks like this

Step 1 - Matrix is non-empty— proceed

Step 2 - The lowest number of 1s in a column is 1

Step 3 - Row D has a 1 in column 5 and is selected

Level 2

Step 4 - Row D is included in the partial solution

Step 5 - Row D has a 1 in columns 3, 5, and 6 which sets the corresponding values in Counts to 0.

Row F remains and columns 2 and 7 remain with Counts = { 2:1, 7:1 }

The continuation here is left as an exercise to the reader.

This results in a terminating solution of [A,D,F] before backtracking

Level 1

Step 4 - Select Row B, including it in the partial solution

Step 5 - Row B has a 1 in columns 1 and 4, reducing the corresponding values in Counts to 0.

Eliminate rows overlapping cols 1 and 4.

Counts = { 2:1, 3:1, 5:1, 6:1, 7:2 }

Step 1 - non-empty, continue

Step 2 - The smallest number of 1s is 1, choose D

Level 2

Here we will choose row F, see that Counts[7] = 1, and terminate unsuccessfully