Generalizing the algorithm for domino tiling?
https://stackoverflow.com/questions/7342389
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
In this earlier question the OP asked the following problem:
Given a rectangular grid where some squares are empty and some are filled, what is the largest number of 2x1 dominoes that can be placed into the world such that no two dominos overlap and no domino is atop a filled square?
The (quite beautiful!) answer to this problem recognized that this is equivalent to finding a maximum bipartite matching in a specially-constructed graph. In this graph, each empty square has a node that is linked to each of its neighbors by an edge. Each domino then corresponds to an edge in the graph such that its endpoints are not covered by any other edge. Consequently, any set of edges that don't share a vertex (a matching) corresponds to an arrangement of dominoes, and vice-versa.
My question is a generalization of this earlier one:
Given a rectangular grid where some squares are empty and some are filled, what is the largest number of M x N dominoes (for a given M and N) that can be placed into the world such that no two dominos overlap and no domino is atop a filled square?
I cannot see how to convert this into a matching problem as was done in the previous case. However, I also don't see any particular reason why this problem would immediately be NP-hard, so there may be a polynomial time solution to the problem.
Is there an efficient algorithm for solving this problem? Or does anyone have a reduction that would show that this problem is NP-hard?
Thanks so much!
Solution
This problem is definitely NP-hard and I can prove it. There is a reduction from 3-SAT to this problem. Specifically, it's a reduction from 3-SAT to the subproblem of this problem in which the dominoes are 1x3. There may also be other reductions for other specific sizes, but this one definitely works.
Essentially, in this reduction, we're going to use domino positions to encode either true or false. In specific, I'm going to adopt the same notation as the other solution, which is to say that I'll use asterisks to indicate open spaces on the grid. I'll also use sets of three capital letters to represent dominoes and lower case letters to represent "signals" which are spaces which may or may not be filled depending on the state of the system.
To embed a 3-SAT problem into this space, we're going to need a set of what I'll call gadgets which allow only certain states to be possible. Most of these gadgets will have a fixed number of dominoes in them. The exception will be the gadgets which represent the clauses which will have one extra domino if the clause is true (satisfied) but not when it is false (unsatisfied). We can interconnect these gadgets using paths. Together this will allow us to build a 3-SAT circuit. We will have a base number of dominoes since each path and gadget will take a standard amount of dominoes, we can add those up to get a base number k and then each clause gadget can have one extra domino if it is true, so if all clauses can be made true (and hence the expression satisfied) and there are n clauses, then the maximum number of dominoes will be n+k. If not, then the maximum number will be less than n+k. This is the basic form of the reduction. Next I will describe the gadgets and give examples.
Similar to the other answer, we're going to have two positions which encode true and false for a given variable. So, I'll start with a single tile which can be in two possible places.
****
This can either be covered with one domino like
AAA* or *AAA
Obviously, this cannot be covered with 2 dominoes and covering it with 0 dominoes would never be maximal. For my purposes, we're going to consider a protrusion to represent the value "false" and a lack of protrusion to represent "true". So we can view this part as having carrying two signals:
x**y
And in this case, only one of x or y will be covered, so we can consider the signals to be x and the logical not of x. For our purposes, whichever is covered is false, whichever is not covered is true. Next, we can transmit signals simply through straight can curved paths. If we have
x*****y
We will again have exactly two dominoes and result in either x or y being covered, but not both.
***y
*
*
x
Will have exactly the same behavior. So we can use this to create long and curving paths in lengths which are increments of 3. However, not all lengths we might want to use are increments of 3, so we need an additional gadget to move a different distance. I call this the fiddler gadget and it's only purpose is to move the signal slightly uneven distances to make things connect successfully. Its input comes from x and output goes to y and it merely transmits the same signal along. It looks like this:
***y
*
**x
It always contains exactly two dominoes and is filled in one of the following two ways:
BBB* ABBB
* A
AAA *AX
If we're going to model 3-SAT, however, we need more than this. Specifically, we need some way to model the clauses. To do this, we have a gadget where one extra domino can be packed in if the clause is true. The clause will be true when one or more of its inputs is true. In this case, that means that we can pack one extra domino in when at least one of the inputs does not protrude. It will look like this:
*x*y*
*
z
If we add an extra path to each for clarity, then it looks like this:
* *
* *
* *
*****
*
****
If x,y, and z are all false, then they'll all have protrusions and it will be filled like this:
A B
C D
C D
*C*D*
*
EEEF
Where the rest of dominoes A,B, and F continue on down a path somewhere. If at least one of inputs is true, then we can pack in one extra domino (G) like so:
C B A D A B
C D C D C D
C D or C D or C D
GGGD* *CGGG *CGD*
* * G
EEEF EEEF GEEE
However, even if all inputs are true, then we cannot pack in more than one domino. That scenario would look like this:
C D
C D
C D
*****
*
*EEE
And as you can see, we can only insert exactly one extra domino into the empty space, not two.
Now, if terms were never repeated, then we'd be done (or very nearly done). However, they can be repeated, so next, we need a signal splitter so that one variable can appear in multiple terms. To do this, we utilize the following gadget:
y*** ***z
* *
***
***
x
In this gadget x is the input and y and z are the outputs. In this gadget, we can always pack 5 dominoes. If x protrudes than packing 5 dominoes will always require covering y and z as well. If x does not protrude, then covering y and z is not required. The packing where x does not protrude looks like this:
yAAA BBBz
C D
CED
CED
E
When x does protrude (we use X to indicate the end of the domino protruding into space x), the maximal packing necessarily covers both y and z:
AAAC DBBB
C D
C*D
EEE
X
I will take a moment to note that it would be possible to pack this with five dominoes when x is not protruding in such a way that either y or z protrude. However, doing so would result in terms which could be true (not protruding) becoming false (protruding). Allowing some of the terms (not variables, but actual terms in the clauses) to differ in value only by becoming false unnecessarily will never result in being able to satisfy an otherwise unsatisfiable expression. If our 3-SAT expression was (x | y | z) & (!x | y | !z) then allowing both x and !x to be false would only make things harder. If we were to allow both ends of something to be true, this would result in incorrect solutions, but we do not do this in this scheme. To frame it in terms of our specific problem, protruding unnecessarily will never result in more dominoes being able to be packed in later down the line.
With paths and these three gadgets, we can now solve planar 3-SAT, which would be the sub-problem of 3-SAT where if we draw a graph where the terms and clauses are vertices and there is an edge between every term and every clause which contains that term, that the graph is planar. I believe that planar 3-SAT is probably NP-hard because planar 1-in-3-SAT is, but in case it's not, we can use gadgets to do a signal crossing. But it's really quite complex (if anyone sees a simpler way, please let me know) so first I'm going to do an example of solving planar 3-SAT with this system.
So, a simple planar 3-SAT problem would be (x | y | z) & (!x | y | !z). Obviously, this is satisfiable, using any assignment where y is true or several other assignments. We will build our dominoes problem thus:
*******
* *
* *
**** ***
* *
*** ****
* *
* *
* ******* *
* * * *
* * * *
*z*x* *****
* *
**** ****
* *
***
***
*
*
*
y
Notice that we had to use fiddlers at the top to get things to space correctly or else this would've been substantially less complex.
Adding up the total dominoes from gadgets and paths we have 1 splitter (5 dominoes), two fiddlers (2 dominoes each), and a total of 13 regular paths, for a grand total of 5 + 2*2 + 13 = 22 dominoes guaranteed, even if the clauses cannot be satisfied. If they can be, then we will have 2 more dominoes which can be filled in for a total of 24. One optimal packing with 24 dominoes is as follows:
QRRRSSS
Q T
Q T
OPPP *UT
O U
*ON UVVV
N W
N W
M IIIJJJK W
M H K X
M H K X
*zGH* LLLX*
G *
GEEE FFF*
B D
BCD
BCD
C
A
A
A
This tiling contains 24 dominoes, so we can know that the original expression is satisfiable. In this case, the tiling corresponds to make y and x true and z false. Notice that this is not the only tiling (and not the only satisfying assignment of boolean values), but that there is no other tiling which will increase the number of tiles beyond 24, so it is a maximum tiling. (If you don't want to count all the dominoes you can note that I used every letter except for Y and Z.)
If the maximal tiling had contained either 22 or 23 dominoes, then we would know that one of the clauses was not satisfied (GGG and/or LLL dominoes would not be able to be placed) and hence we would know that the original expression was not satisfiable.
In order to be certain that we can do this even if planar 3-SAT isn't NP-hard, we can build a gadget which allows paths to cross. This gadget is unfortunately kind of big and complex, but it's the smallest one I was able to figure out. I'll first describe the pieces and then the whole gadget.
Piece 1: Crossover point. x and y are the inputs. a,b,and c are the outputs. They will need to be combined using other gadgets to actually relay x and y to the opposite side of each other.
***c
*
***
* *
* *
* *
***
***
ax*yb
This gadget will always fit exactly 7 dominoes. There are four possible input combinations. If neither input protrudes (both are true) than no output will protrude and it will be filled as in (tt1) or (tt2) below. If only input x protrudes then only c will protrude as in (ft) below. If only input y protrudes then either output a or c will protrude as in (tf) below. And if input x and y both protrude then output c protrudes as in (ff) below.
(tt) AAAc (ft) AAAc (tf) AAAc (ff) BAAA
* * * B
BBB BBB BBB CBD
C D C D C D C D
C D C D C D C D
C D C D C D E G
EEE EEE EEE EFG
FFF FFF FFF EFG
aGGGb aXGGG GGGYb aXFYb
I have not included the possibility that in the (ft) or (tf) scenarios that c could be covered instead of a or b. This is possible within the scope of this gadget but once combined with other gadgets to form the complete crossover, if it were to do so, it would never result in a larger number of clauses being satisfied so we can exclude it. With that in mind, we can then observe that in this case the value of the input x is equal to the value of b & c and the input y is equal to the value of a & c (note that this would be logical or rather than logical and if protrusion were considered true rather than false). So we just need to split c and then use a logical and gadget to connect connect the values of c with a and b respectively and we will then have successfully completed our cross over.
The logical and is our simplest gadget so far and it looks like this:
****
*
x*y
You might actually note that there's one embedded towards the top of the crossover point gadget. This gadget will always contain precisely 2 dominoes. One will be at the top to serve as the output. The other one serves as a switch which will be horizontally oriented only if both x and y are true (non-protruding) and vertically oriented otherwise as we can see in the following diagrams:
BBB* ABBB ABBB ABBB
* A A A
AAA XAy xAY XAY
Thus we can complete the crossover by splitting c and then adding two of these gates, one for a & c and one for b & c. Putting it all together requires also adding some fiddler gadgets and looks like this:
******* ****
* * * *
* *** *
*** *** ***
* * *
**** * ****
* * *
* **** *
*** * ***
* *** *
**** * * ****
y * * * * x
* * * * * *
* **** *** **** *
*** *** ***
**********x*y*************
I'm not going to fill in example tilings for that. You'll have to do it yourself if you want to see it in action. So, hooray! We can now do arbitrary 3-SAT. I should take a moment to note that doing this will be a polynomial time transformation because even in the worst case, we can just make a big grid with all of the variables and their opposites along the top and all the terms on the side and do O(n^2) crossovers. So there is a simple, polynomial-time algorithm for laying this all out and the maximum size of the transformed problem is polynomial in the size of the input problem. QED.
Edit note: Following Tom Sirgedas's excellent work in finding a mistake in the splitter gadget, I've made some changes to the answer. Essentially, my old splitter looked like this and could be packed with 6 when x does not protrude (rather than the 5 I had intended) like this:
y*** ***z AAAC DBBB
* * C D
*** C*D
*** EEE
*x* FFF
So I revised it by removing the two spaces on either side of x. This eliminates the six domino packing while still allowing a 5-domino packing in which y and z are uncovered when x is uncovered.
OTHER TIPS
To Keith:
Great work and great explanations! Though, I wrote a program to find maximum tilings, and it uncovered a flaw. Hopefully this can be fixed! [Update: Keith did fix the problem!]
Please check out this link: http://pastebin.com/bABQmfyX (your gadgets analyzed, plus very handy c++ source code)
The problem is that the gadget below can be tiled with 6 dominoes:
y*** ***z
* *
***
***
*x*
-Tom Sirgedas
Really a good question. This problem is equivalent to finding the size maximum independent set (or maximal clique size) on a special graph - the vertices would be all possible positions of the MxN rectangle and edges would connect the two positions if they collide. Then finding the size of maximum independent set yields the result. Or vice versa, we could define the edge as connecting two positions which do not collide, then we would look for maximum clique size. Anyway, neither graph is neither claw-free nor perfect, so we cannot use polynomial solutions to find maximum independent set / clique.
So, we could try to convert the maximum independent set problem to this tiling problem, but I couldn't find a way how to convert the general graph to this, because you cannot convert e.g. induced K1,5 subgraph to the tiles.
The first thing I would do is make a third state: "empty, but unreachable". You can easily prove each tile unreachable in l*w*m*n time (where l is length of the world, w is width of the world, and m and n are dimensions of the tile). This will reduce your space such that any empty tile is reachable. Note that you may have islands of reachable tiles. The simplest example of this is that the world is cut in half. This lends itself to a recursive effort where each island of reachability is treated as a world in and of itself.
Now that we're dealing with an island (which may or may not be square) you essentially have a special case of the 2D knapsack problem, which is known to be NP-hard (citation under Previous Work). Yours increases complexity of the problem by adding fixed positions in the knapsack that always filled, but reduces complexity (slightly) by making all packages the same size.
1x3 tiles are hard by reduction from cubic planar monotone One-in-three 3SAT. We have to build some "circuitry" to encode the formula.
"Gates":
X********Y
Forces exactly one of X and Y to be covered externally. Used to link a variable and its negation.
Y***
*
*
ooo ****
* * * *
* * * *
X **** Z
Forces none or all of X and Y and Z to be covered externally. Used to copy X or destroy three copies of the same thing. Wires can be shaped more or less arbitrarily using length-3 L pieces.
*******************
* * *
* * *
X Y Z
Forces exactly one of X and Y and Z to be covered externally. One for each clause.
