Inexact cover, or cover with gaps

Question

Dancing Links: wikipedia article, research paper is an implementation of algorithm X for exact cover problem.

In the Knuth's research papaer, linked above it is shown how Polymino problem (that is covering a given shape with given sets of Polymino) is translated to exact cover problem, so that dancing links can be used to solve it.

Exact Cover problem goes like this:

Given a matrix of 0s and 1s, find a subset of rows with exactly one 1 in each column.

For example the matrix

is solved by choosing rows 1, 4 and 5.

Knuth explains in the paper, how the Polymino problem can be translated into exact cover problem on example of the famous case of Polymino problem where we are trying to cover chess board (8x8) with 12 pentominoes. The 12 pentominoes occupy 60 squares in total, so 4 spaces on the 64 squares chessboard are left unaccounted.

Here is Knuth's explanation, of how the problems are translated into each other:

Imagine a matrix that has 72 columns, one for each of the 12 pentominoes and one for each of the 60 cells of the chessboard-minus-its-center. Construct all possible rows representing a way to place a pentomino on the board; each row contains a 1 in the column identifying the piece, and five 1s in the columns identifying its positions. (There are exactly 1568 such rows.)

If this is not very clear please refer to the original paper for further details.

This makes sense. Latter in the paper Knuth uses a 2x2 tetromino to account for the 4 squares mentioned earlier. This also makes sense.

Now imagine that you have a different shape of the board. This is easy. You still translate each square into a matrix column as explained above.

What I'm having problems though is when I need to find solution for "inexact" cover, or cover with gaps.

In the chessboard problem above, imagine, that you do not want to settle for nicely defined 2x2 tetromino in the centre, like Knuth does. Instead you want to find all solutions no matter where the four "missing" squares go onto the board.

My initial idea was model this with 4 separate "monomino" one square each. Unfortunately this does not work so well. There are over 6 millions combinations of how 4 squares can be selected from 64 square keyboard.

If we assume that for a particular solution the monominoes occupy square A, B, C and D, then there are 4! of indentical solutions that the algorithm need to wade through, where monomino 1 goes to square A, monomino 2 goes to square B, etc or monomino 1, goes to square B , monomino 2 goes to square A, etc and all other possible combinations of fitting these 4 pieces into these 4 squares.

If we have a problem when we have more than 4 gaps, this becomes even worse. We are getting more and more identical solutions where only placement of monomino order is different, and the squares they occupy are the same.

This makes the algorithm orders of magnitudes slower, since in needs to enumerate all these identical solutions.

I cannot figure out how to efficiently model the problem of covering a shape with polymino pieces when there are many gaps as explained above.

Are there better ways to model it?

Answer 1

I'd propose this idea:

Let the algorithm run almost naturally, but if it encounters a shortest column that has no options left, do not backtrack immediately. Instead, ignore that column and pick another one. Do this up to four times per iteration. Once more than 4 columns have no options, do backtrack as you normally would.

This will eventually run until a solution is found, in which 4 cells will be left unassigned.

By allowing 4 option-less columns, you place no required knowledge on which columns (cells) should be left unoccupied. The matrix is kept small and tidy as before.

Performance: The search tree probably does not grow too vast, as most of the "stupid" piece placements will trigger the limit within 1 or 2 iterations. Accordingly, the tree should only be about one order of magnitude larger than usual.