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

enter image description here

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?

  • $\begingroup$ You say the resulting algorithm might be slow, because there are so many cases to explore. I have two responses. (1) Have you tried it? Have you tried running Knuth's algorithm on the resulting exact cover instance? It would be interesting to know if it works or not. (2) The problem is NP-hard. I don't find it too surprising that it may be slow. It's possible there might not be any good solution. Still fair to ask whether one can do better, but just preparing you for the possibility that there might not be a better solution. $\endgroup$ – D.W. Aug 21 '18 at 21:23
  • $\begingroup$ @D.W. I tried it for 6 by 6 sqaure with 7 default tetromino, fixed to a particular orientation, that is not flips or rotates - to make it easier. This gives 8 gaps. So each feasible solution gives me (8! = 40320) duplicates. Getting that many solutions and then trying to eliminate duplicates feel sub-optimal. It feels like a better level is either changing the model or adjusting the algorythm. As for NP-hard - yes, I realize that. But I'm using smaller board than in original research and I have better than Pentium III used in the original research (we all do now). $\endgroup$ – Andrew Savinykh Aug 21 '18 at 21:29

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.

| cite | improve this answer | |
  • $\begingroup$ Thank you for this. I'm afraid I've lost the source code since the question was asked, so it is not likely, that I'll follow up on this again soon. $\endgroup$ – Andrew Savinykh Jun 12 at 21:24
  • $\begingroup$ Thanks for the info; no worries :) $\endgroup$ – mafu Jun 12 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.