Is Dominosa NP-Hard?

Question

Dominosa is a relatively new puzzle game. It is played on an $(n+1)\times(n+2)$ grid. Before the game begins, the domino bones $\left(0,0\right),\left(0,1\right),\ldots,\left(n,n\right)$ are placed on the grid (constituting a perfect tiling). In the next step, the domino bones are hidden, leaving only the numbers revealed. The purpose of the game is to recover the original arrangement of the domino bones. You can play the game here: http://www.puzzle-dominosa.com/:

Rules:

The rules are simple. You have to find the location of all the dominoes on the grid. A domino is a pair of numbers. You can only have one of each pair.

I have some polynomial algorithms that solve a relatively small part of the puzzle. I could also show that typical Dominosa grids have at least $2^{\frac{n}{2}+o\left(n\right)}$ solutions.

Is Dominosa NP-Hard?

Answer 1

Note: This is a continuation and revision of my other answer.

Problems with the reduction

Recall the decision problem:

Is there a perfect tiling covering a given a $(n+1) \times (n+2)$ grid with $n$ unique tiles?

So for an $(n+1) \times (n+2)$ grid, we can only use $n$ variables.

But:

• Our reduction requires a lot of unique variables, much more than $\mathcal O(n)$.
• Furthermore, our wires are open ended, which leads to:
  • How do we know we can tile the open areas?

To solve the first problem, we artificially make the game-board much larger; essentially we make $n$ equal to the number of variables we actually require, then create a grid of size $(n+1)\times(n+2)$, and place our grid in the lower left corner. This will lead to a quadratic blowup.

For the second problem, we must rethink our gadgets a bit.

It can seem a little daunting to prove that we can successfully tile the rest of the board according to the rule. So we start off with the same strategy one would use to actually generate game-boards of size $(n+1)\times(n+2)$:

First we generate a set of all possible tiles. All of these tiles will have to be placed on the board. Then we remove the tiles, and leave behind their squares.

However, our gadgets don't guarantee a particular set of tiles will be placed; the tiles placed depend on the state. So we must carefully modify the gadgets to guarantee particular tiles will be removed, no matter which state is chosen.

Let's go over our gadgets then.

The wire and clause-gate are problematic for two reasons.

1. We don't know that the squares surrounding a wire or clause-gate can be tiled correctly; after all, some wires can be pushed to the left, others to the right, and tiling the remaining white-space squares becomes non-trivial. We'll refer to this problem as the "flow" problem.
2. There is no way of knowing which tiles to remove from the tile-set; in one state, one set of squares, in the wire or clause-gate, will be tiled, in another state, an entirely different set of squares will be tiled.

To solve these issues:

• First, we generate a set of all possible tiles. All of these tiles will have to be placed on the board; as we place them on the board, we will remove the tile from the set. Though we might not at first know $n$, since we have yet to fully describe the formulation, we can add all the new tile possibilities as we increment $n$, as needed. All of the tiles we remove from this set must guaranteed be placeable (at least, be guaranteed to be placeable if the formula is satisfiable). We call removing a tile from the tile-set, to "discharge" the tile from the tile-set, as in to discharge our obligation to place it on the game-board.
• We must carefully design the gadgets to guarantee particular tiles will be removed, no matter which state is chosen.
• We must close our gadgets, so that they don't push tiles all around the board depending on their state; rather all of their states must only take up a particular well defined area.
  • Alternatively, all of their states must be guaranteed to be able to take up a well defined area; this guarantees a satisfiable tiling, but does not guarantee that a particular tiling will occur. This is the same way a Dominosa game is made:
    • First the tiles are generated into a set;
    • Then the tiles are placed down in a random configuration,
    • As each tile is placed, it is removed from the tile-set.
    • Then the tiles are removed from the board, leaving behind their squares.
    • This does not guarantee that the intended configuration will be chosen,
    • Rather, it guarantees that the intended configuration is able to be chosen, and thus a solution exists. We can do the same thing here.
• After placing all the gadgets of the formulation, instead of placing unique ${\star}$ squares by default, i.e. on all "whitespace", we make sure the whitespace is a rectangular area with one even dimension, or break down the whitespace into rectangles with one even dimension, and we simply tile the whitespace with the remaining tiles in the tile-set.
• After placing all the tiles from the set, we know everything is placeable.
  • Some tiles will be obviously placeable, such as those in walls, others will be placeable only iff the formula is satisfiable, due to the nature of the relationships between the gadgets.
• Then we remove the tiles, and leave behind their squares.

Let's go over our gadgets then.

Forcing gadget

We can make an arbitrary number of building blocks by making sure they each can't be paired with themselves.

For example, let us say we want to force a $\mathbf{({1}{\star},{1}{\star})}$ tile, so that we can use $\mathbf{1}{\star}$ as a building block. (note, ${1}{\star}$ is an arbitrary variable, which we want to force as pair to itself, not necessarily a building block as we used the $1$ value previously)

To guarantee that our $\mathbf {1}{\star}$-building-block reserves $\mathbf{({1}{\star},{1}{\star})}$, we will place it against the bottom wall in the following configuration: we will place the reserved number, let us call it $\mathbf{1}{\star}$ against the wall like an up-tack (shaped like $\bot$); $3$ against the wall, and one in the 2nd row in the middle. Then we will place another two numbers, let us call them ${\mathbf 2}{\star}$ and ${\mathbf 3}{\star}$; these are unique to this gadget. We place these on top of the left and right $\mathbf{1}{\star}$.

Illustrated below, shared black border is the bottom of the game-board, description from left-to-right.

• Configuration of the gadget. Each ${\mathbf 2}{\star}$ and ${\mathbf 3}{\star}$ here are unique to this gadget.
• The 3 possible states of tiling the center $\mathbf{1}{\star}$.

After doing this, we can guarantee that our gadget can be tiled with a specific set of tiles, while guaranteeing that our gadget must force the $\mathbf{({1}{\star},{1}{\star})}$ pair.

• We know that $\mathbf{({1}{\star},{1}{\star})}$ must occur, because all 3 possible tiling states of the lower middle $\mathbf{1}{\star}$, tile as $\mathbf{({1}{\star},{1}{\star})}$, as illustrated in the figure on the right, above.
• The remaining tiles can be tiled as $({1}{\star},{2}{\star})$ and $({1}{\star},{3}{\star})$, covering the gadget. Thus, we can remove those tiles from our global tile-set. Illustrated below.

Description, left to right:

• Left, top: Left state, Left, bottom: A valid tiling of the remaining squares.
• Middle, top: Middle state, Middle, bottom: A valid tiling of the remaining squares.
• Right, top: Right state, Right, bottom: A valid tiling of the remaining squares.

Note, that the tiling of the remaining squares isn't forced, since they can tile with nearby neighbors instead of $\mathbf{1}{\star}$, but since it is a valid tiling of the game-board in all of the states, we can remove them from the tile-set, and assume they will be tiled in exactly that way. Since we know there is a valid possible tiling, we have at least one possible tiling of the game-board, if the formula is satisfiable. Though there is no guarantee that these will be tiled this way, there is a guarantee that the $\mathbf{({1}{\star},{1}{\star})}$ tile will be forced.

Note: if you aren't satisfied with this, or are confused by the difference of "being able to tile" vs. "being forced to tile", you can simply place a wall around the $3\times 2$ gadget, the same way we make a $3\times 2$ wall below for the clause-gadget.

This gadget is not closed, because it doesn't need to be (but you can if you want to). It doesn't need to be, because it has a feasible configuration, which we can remove from the tile-set. Although it might be possible to do a different configuration, this does not affect the satisfiability of the problem.

The following tiles are guaranteed to be to be tiled (thus can be removed from the tile-set): $\mathbf{({1}{\star},{1}{\star})}$

The following tiles are guaranteed to be able to be tiled (thus can be removed from the tile-set): $({1}{\star},{2}{\star}), ({1}{\star},{3}{\star})$

If you choose to close this gadget with a wall, then $({1}{\star},{2}{\star}), ({1}{\star},{3}{\star})$ will also be guaranteed to be covered.

New Wire and Clause gates

Because of the problems of flowing, and the emptying the tile-set, we need to redesign the wire a bit.

One way to solve the flow problem, is to make the wire a circuit, instead of just simple left-right states; that is, it would be circular instead of a line, and therefore if the top part of the circle is pushed right, the bottom will be pushed left. This solves the flow problem.

Following this route, we can change the wire and clause gate to solve both problems.

Reserving $\mathcal T$ and $\mathcal F$

Let us introduce two new universal values, $\mathcal T$ and $\mathcal F$. These two values are universal; actual values in the grid, such as square-values $2$ and $3$ (since by convention, we reserved $1$ as a building block for walls), or whatever you choose. They represent true and false, respectively.

We force-reserve the tiles $(\mathcal T, \mathcal F)$, $(\mathcal T, \mathcal T)$, $(\mathcal F, \mathcal F)$, as follows; illustration below, description from left to right:

• We use the same scheme as forcing any $\mathbf{({1}{\star},{1}{\star})}$ tile, using $\mathcal T$ as $\mathbf{1}{\star}$. Each ${\mathbf 2}{\star}$ and ${\mathbf 3}{\star}$ here are unique to this gadget.
• We use the same scheme as forcing any $\mathbf{({1}{\star},{1}{\star})}$ tile, using $\mathcal F$ as $\mathbf{1}{\star}$ Each ${\mathbf 2}{\star}$ and ${\mathbf 3}{\star}$ here are unique to this gadget.
• We use the same scheme as forcing a $\mathbf{({1}{\star},{1}{\star})}$ tile, using $\mathcal F$ as $\mathbf{1}{\star}$ in the center, and using $\mathcal T$ in the other locations of the up-tack. This forces $(\mathcal F, \mathcal T)$ to tile. ${\mathbf 2}{\star}$ and ${\mathbf 3}{\star}$ are able to tile with $\mathcal T$, so we remove them from the tile-set. Each ${\mathbf 2}{\star}$ and ${\mathbf 3}{\star}$ here are unique to this gadget.

Wire

Each wire will start and end with a value, let us call it ${A}{\star}$, which is unique the to wire. For each clause the wire participates in, the wire will have two wire-values, ${x}{\star}$, and ${x'}{\star}$, which are unique to each wire, and participate in the same clause. Illustration below, with description from left to right.

• A wire that participates in one clause. The wire has a height of $2$, and has a length of $2*p+3$, where $p$ is the number of clauses the wire participates in. The wire is padded by two ${A}{\star}$ squares on the left, and two on the right. It is, of course, surrounded by a wall on all sides, indicated by the blue outline. Note, that the ${1}{\star}$ is unique to this wire, and will only be used in the wire, and the clause it participates in.

Illustrated below are the two states, descriptions from left to right.

• A wire that participates in one clause, in the true state. The wire is considered true, when the ${x}{\star}$ squares are paired with a $\mathcal T$ squares, and the ${x'}{\star}$ squares are paired with $\mathcal F$ squares. It is considered false in the other state, where the tiling is reversed. Note how the tiling is forced once the ${A}{\star}$ tile is selected: $(\mathcal T,\mathcal F)$ are already forced earlier, thus the rest of the tiles must be horizontal.
• The same wire in the false state.

When participating in more clauses, there are more value ${x}{\star}$, and ${x'}{\star}$, one pair for each clause the wire participates in. They alternate being on top and bottom, as does the $\mathcal T$ and $\mathcal F$ squares that separate each ${x}{\star}, {x'}{\star}$ pair.

The two corresponding states.

This gadget is closed, thus there is no "flow problem".

Note how in either state, we collect the following tiles, no matter the state: $({A}{\star},{A}{\star})$, $({A}{\star},\mathcal T)$, $({A}{\star},\mathcal F)$.

There are some tiles however, that we are unsure of; in one state we can remove $({1}{\star}, \mathcal T), ({1'}{\star},\mathcal F), ({2}{\star},\mathcal T), ({2'}{\star},\mathcal F) ...$ from the tile-set, while in another state we can remove $({1}{\star}, \mathcal F), ({1'}{\star},\mathcal T), ({2}{\star},\mathcal F), ({2'}{\star},\mathcal T) ...$ from the tile-set, so which tiles can we actually remove? The answer is: the clause gate has the same problem, but with the opposite set of tiles. It will always collect the remaining, opposite, and uncollected tiles, as we will see in the next section. Since each of these is paired with a clause gate, we will be able to remove them both.

Clause

Next we will create the first iteration of the new clause gate. It consists of a $2\times 3$ gadget, enclosed by walls. Inside the gadget, we place one $\mathcal F$ in the top-center, and two $\mathcal T$ squares in the lower corners; one in the lower-left, and one in the lower-right. The remaining squares will be values representing wire-variables of three different wires. Let us call these ${a}{\star}, {b}{\star},$ and ${c}{\star}$. The $\mathcal F$ will be forced to pair with one of the wire-variables, and the remaining wire-variables will pair with the $\mathcal T$ values. Illustrations below, descriptions from left to right.

• Left: The configuration for the first iteration of the new clause-gate.
• Right The three possible states of the $\mathcal F$ tiling.

These three states leads to three possible tilings. Illustration below, descriptions from left to right.

• Left, top: $\mathcal F$ tiled left, Left, bottom: Tiling the remaining squares.
• Middle, top: $\mathcal F$ tiled right, Middle, bottom: Tiling the remaining squares.
• Right, top: $\mathcal F$ tiled down, Right, bottom: Tiling the remaining squares.

Since the $\mathcal F$ will be paired with one of the wire-variables in the clause, that wire-variable can no longer be paired with $\mathcal F$ in the wire; thus forcing the wire to true. Conversely, the remaining wire-variables that tile with $\mathcal T$ will be forced to tile with $\mathcal F$ within their wires. This is exactly the same constraints as a $\rm 1\text{-in-}3\text{-}S{\small AT}$ clause.

Note, ${a}{\star}, {b}{\star},$ and ${c}{\star}$ are wire-variables, but they could each refer to an ${x}{\star}$ or an ${x'}{\star}$ wire-variable; using an ${x'}{\star}$ is essentially negating the wire-variable.

One addition: to discharge the obligation of knowing which tiles can be removed from the tile-set, we have to "double and contrapositive" the clause. What I mean by this, is to make another $3\times 2$ gadget, with $3$ additional variables representing the negations of ${a}{\star}, {b}{\star},$ and ${c}{\star}$. Let us call these ${a'}{\star}, {b'}{\star},$ and ${c'}{\star}$. These must be the negated variable-wire values of ${a}{\star}, {b}{\star},$ and ${c}{\star}$. This $3\times 2$ gadget is different, in that it will have a $\mathcal T$ at the center, and two $\mathcal F$ values at the corners; exactly the opposite of the clause gadget described thus far. By "doubling" the clause like this, we re-add the same constraints as the gadget described above. However, we also discharge all the combinations of $(\mathcal T, {x}{\star}), (\mathcal T, {x'}{\star}), (\mathcal F, {x}{\star}), (\mathcal F, {x'}{\star})$ from the tile-set, for each variable (and thus for ${a}{\star}, {b}{\star},$ and ${c}{\star}$ as well, because they are after all, wire-variables). Illustrated below, descriptions from left to right.

• A "double and contrapositive" clause. The bottom section is the clause described above; the top section is the newly described contrapositive clause. The new clause has exactly the same logical constraints; it is the contrapositive of the bottom clause. Together, these combined gadgets and the wire discharge all of the combinations of $(\mathcal T, {x}{\star}), (\mathcal F, {x}{\star}), (\mathcal T, {x'}{\star}), (\mathcal F, {x'}{\star})$ from the tile-set, for each wire-variable participating in the clause.
• The blue line in the middle of the left-most figure is there for ease-of-viewing; in reality it can be removed without allowing any more states.

So, let us take an example, to show that all the tiles get discharged as promised. Illustrated below, description from left to right.

• Figure of a wire participating in a single clause; a state is chosen for the clause. Here, we are using ${1}{\star}={b}{\star}$, while ${a}{\star}$ and ${b}{\star}$ are representing other wire-values in this clause.
• For the given state in the clause, the ${1}{\star}$ value is forced to be paired with the neighboring $\mathcal T$.
• This causes the wire to be forced to be true-valued (you can tell as the positive variable of the wire is forced to pair with the $\mathcal T$, and the negative variable is forced to pair with the $\mathcal F$, as explained above).
• This forces the ${1'}{\star}$ in the contrapositive clause (the upper section of the clause) to be paired with $\mathcal T$ within the clause. Now if you look at the wire, every tile within the wire is guaranteed to be discharged: either discharged in the wire itself, or in the corresponding clause-gadget. In this state, we have the tiles, $({A}{\star},{A}{\star})$, $({A}{\star},\mathcal T)$, $({A}{\star},\mathcal F)$, $({1}{\star},\mathcal T)$, $({1}{\star},\mathcal F)$, $({1'}{\star},\mathcal F)$, and $({1'}{\star},\mathcal T)$.

Trying the other state, we get the illustration below, description from left to right.

• The clause is in the other state, tiling $({1}{\star},\mathcal T$ in one of two ways.
• Therefore, $({1}{\star},\mathcal F$ is forced on the wire,
• Leading the rest of the wire to tile correspondingly, and value the wire as false.
• Finally, in the contrapositive/upper section of the clause-gadget, $({1'}{\star},\mathcal F)$ must tile, because $({1'}{\star},\mathcal T)$ is taken in the wire. In this state, we have the tiles, $({A}{\star},{A}{\star})$, $({A}{\star},\mathcal T)$, $({A}{\star},\mathcal F)$, $({1}{\star},\mathcal T)$, $({1}{\star},\mathcal F)$, $({1'}{\star},\mathcal F)$, and $({1'}{\star},\mathcal T)$. These are the same tiles discharged as in the other state.

Thus in either state, we discharge the same tiles. Therefore, the wire and clause together successfully discharge specific tiles iff there is a satisfying assignment.

This gadget is closed, so there won't be a flow problem. The clause-gadget together with the wire gadget are guaranteed to always discharge the same tile-pair values, and thus we can discharge these even if we don't know which way it will tile.

Now all of our gadgets fulfill the criteria.

Formulation

In our final formulation, we create three rows of gadgets, each separated by a horizontal wall.

• On the bottom, we place the forcing-gadgets, which are two tiles tall. We need a forcing gadget for the building block, and for combinations of $\mathcal T$ and $\mathcal F$. We place the forcing gadgets directly next to each-other.
• In the middle row, we place the wire gadgets, horizontally, which are two tiles tall. The wire gadgets should be separated from each-other with a vertical wall.
• In the top row, we place clause gadgets, which are four tiles tall. The clause gadgets should be separated from each-other by a vertical wall.

Illustrations follow, descriptions above each figure. Click images for full resolution. Source code to reproduce/generate the images is listed at the bottom of the page.

Using the formula $\Phi(\mathbf x)= (x_1,\neg x_2, x_3) \wedge (x_2,\neg x_3,x_4) \wedge (x_1,x_2,\neg x_4)$ as an example, we have a satisfying solution $(\neg x_1,x_2,x_3,\neg x_4)$ as a witness.

First we start with the horizontal walls separating the rows of gadgets. We show the squares, and the pairs that are forced to tile within the walls.

Next, we show the gadgets. The blue outline represents the borders of the gadgets; dashed blue for the forcing-gadgets, since they will not be surrounded by walls. Note the line in the middle of the clause gadget is not surrounded by a wall; it is there for ease-of-viewing; taking the line away does not allow any more states to occur in the clause, as explained above, but we show the blue line for this demonstration. Note: that we use square-names to give the numbers semantic readability, when applicable. Each name represents a numeric value.

Here we fill in the vertical walls.

Here we fill in the witness solution; i.e this is the tiling solution if using the SAT solution to generate it.

Next we tile the filler-area; the rest of the board, as large as needed, for as large as $n$ is required to tile thus-far. Thus we discharge the remaining pairs in the tile-set. The dashed lines here represent a valid-but-not-forced tiling; there might be another way of tiling these. Here we show the lower-left corner.

Here we fill in the remaining squares with a trivial valid tiling.

Here we show the lower right corner of the grid.

Here we show the upper right corner of the grid. Note how the vertical tiles no longer fit; so we tile the top row horizontally, if necessary.

And finally the top-left corner.

Generating the entire game-board at once via TeX fails with out-of-memory errors from pdflatex, so if you want to see it, you would have to generate clips and patch them together. Be sure to check out the notebook viewer.

---

TikZ sources

• Dominosa.Part.I.tex (writelatex)
• Dominosa.Part.II.tex (writelatex)
• Dominosa.Part.III.tex (writelatex)
• Dominosa.Part.IV.tex (writelatex)
• Dominosa.Part.V.tex (writelatex)

Game generator:

• graphtex.py

  Converts TeX to svg, using pdflatex, pdfcairo (poppler), and rsvg-convert (libsvg)

• dominosa.py

  Contains the conversion logic, game-solution verification, and drawing logic

• dominosa_demo.py

  An executable demo that generates the images used in the answer above. Dumps images to the current-working-directory.

• dominosa_demo.ipynb

  An ipython demo that generates the images used in the answer above.

  • See the notebook viewer to see the results

Answer 2

${\rm D{\small OMINOSA}}$ is NP-hard

---

Playing the game is an optimization problem; finding a valid domino tiling such that it covers all the squares. The decision version of this problem is:

Is there a perfect tiling covering a given a $(n+1) \times (n+2)$ grid with $n$ unique tiles?

Obviously, the optimization problem, the problem of actually finding a solution to the game is at least as hard, or harder, than the decision problem.

We will convert a $1\text{-}3\text{-in-}{\rm S{\small AT}}$ formula to a corresponding grid, that will only be coverable iff there is a satisfiable assignment to the formula. Furthermore, the covering can actually be used to recover the satisfying assignment.

Therefore, if the construction presented is correct, and one could solve a game in polynomial time on a DTM, then it would imply ${\rm P=NP}$. This implies ${\rm D {\small OMINOSA}}$ is NP-hard.

Reduction from $1\text{-}3\text{-in-}{\rm S{\small AT}}$ to ${\rm D {\small OMINOSA}}$

Introduction

Most of the $3\text{-}{\rm S{\small AT}}$ problems/variants have a pretty good correspondence to ${\rm C{\small IRCUIT}S{\small AT}}$. It can be important to think of the problems in parallel; as they are related to each-other, almost anything in one problem can be related to in the other.

${\rm C{\small IRCUIT}S{\small AT}}$ has a planar variant, to which it reduces, called ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$. This conversion is very elegant, and basically allows you to take any planar embedding, find the remaining crossing wires, and use a "gadget" to let the wires cross via a planar "gate" (collection of gadgets, with input and output wires).

Conveniently, most of the $3\text{-}{\rm S{\small AT}}$ variants also have reductions to planar variants, which parallel ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$, and are very related; easily reducible from one to another, and easy to reason about. So whenever I come to a planar problem that might be NP-hard, I think in terms of the planar variants of $3\text{-}{\rm S{\small AT}}$, and their parallels in ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$.

The planar variants are important to know, because they make help make reductions to planar/geometric problems, like Euclidean TSP (incidentally a pretty rare reduction to find and learn). Thus, there is ${\rm P{\small LANAR}}\text{-}3\text{-}{\rm S{\small AT}}$, and a parellel, ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$, to aid in such reductions.

Other $3\text{-}{\rm S{\small AT}}$ variants are important to know because some of them are weaker; that is, seemingly "easier", yet still NP-complete. They seem easier to solve at first glance - and they are much simpler - yet are still NP-complete. NP-complete, but simpler; and therefore easier to make reductions to, in many cases.

For example, there is $1\text{-in-}3\text{-}{\rm S{\small AT}}$. For some problems, you can easily make an exactly $1\text{-in-}3$ gadget, while making "at least 1 in 3", like the standard $3\text{-}{\rm S{\small AT}}$ uses, would be non-obvious and make for huge constructions.

Another example is ${\rm M{\small ONOTONE}}\text{-}1\text{-in-}3\text{-}{\rm S{\small AT}}$. Monotone makes things a lot simpler when you have a construction that can't easily negate values.

Even more amazing is that ${\rm M{\small ONOTONE}}\text{-}1\text{-in-}3\text{-}{\rm S{\small AT}}$ has a planar variant: ${\rm P{\small LANAR}}\text{-}{\rm M{\small ONOTONE}}\text{-}1\text{-in-}3\text{-}{\rm S{\small AT}}$! So this makes things a lot easier; you don't have to cross "wires" (remember, there are parallels in ${\rm C{\small IRCUIT}S{\small AT}}$ to these), and trust me, while crossing gadgets are fun to make, they tend to be very non-obvious and difficult.

$$ \begin{array}{c|c|c|ccc} &&&&\hspace{1em}&\hline\\ {\rm\mathbf{P{\small ROBLEM}}} &\scriptsize{{\rm\mathbf{MONOTONE}}} &\scriptsize{{\rm\mathbf{PLANAR}}} &\scriptsize{{\rm\mathbf{1\text{-in-}3}}} &&{\rm\mathbf{NP\text{-}hard}} \\ \hline\\ {\rm\mathbf{3\text{-} S{\small AT}}} & \text{No} & \text{No} & \text{No} && \text{Yes}\\ \hline\\ {\rm\mathbf{M{\small ONOTONE}\text{-}3\text{-} S{\small AT}}} & \text{Yes} & \text{No} & \text{No} && {\text{No}}^1\\ {\rm\mathbf{P{\small LANAR}\text{-}3\text{-} S{\small AT}}} & \text{No} & \text{Yes} & \text{No} && {\text{Yes}}^2\\ {\rm\mathbf{1\text{-in-}3\text{-} S{\small AT}}} & \text{No} & \text{No} & \text{Yes} && {\text{Yes}}^3\\ \hline\\ \genfrac{}{}{0}{1} {\rm\mathbf{P{\small LANAR}}} {\rm\mathbf{1\text{-in-}3\text{-} S{\small AT}}} & \text{No} & \text{Yes} & \text{Yes} && {\text{Yes}}^4\\\\ \genfrac{}{}{0}{1} {{\rm\mathbf{M{\small ONOTONE}\text{-} }}} {{\rm\mathbf{1\text{-in-}3\text{-} S{\small AT}}}} & \text{Yes} & \text{No} & \text{Yes} && {\text{Yes}}^5\\\\ \genfrac{}{}{0}{1} {{\rm\mathbf{P{\small LANAR}\text{-}}}} {{\rm\mathbf{M{\small ONOTONE}\text{-}3\text{-} S{\small AT}}}} & \text{Yes} & \text{Yes} & \text{No} && {\text{Yes!}}^6\\ \hline\\ \genfrac{}{}{0}{1} {{\rm\mathbf{P{\small LANAR}\text{-}M{\small ONOTONE}\text{-} }}} {{\rm\mathbf{1\text{-in-}3\text{-}S{\small AT}}}} & \text{Yes} & \text{Yes} & \text{Yes} && {\text{Yes}}^7\\ \end{array} $$

1. Pure literal elimination
2. Schaefer's dichotomy theorem
3. The Problem of Compatible Representatives
4. Minimum Weight Triangulation is NP-Hard
5. Schaefer's dichotomy theorem
6. Finding Perfect Auto-Partitions is NP-hard
7. Optimal Binary Space Partitions in the Plane

---

One way to start with a reduction, is to try to find "gadgets" that resemble wires, and a gadget that resembles a clause of one of the $3\text{-}{\rm S{\small AT}}$ variants. As a bonus, many of the variants are planar, we can probably get away without crossing wires.

What is a "gadget"? A gadget is some construction in the problem, that is helpful as a building block to build gates/wires/clauses. Some gadgets will have a restricted set of states; for example, a gadget with two states can be used as a variable; one state is "true" and the other is "false". A gadget with two states, that can be "long", can bend, and split, is useful as a wire - if it can interact with a variable, and become constrained to extend the state of the variable to another location. A gadget with exactly three states can perhaps be used as a clause; if it can be used to constrain "one of three" wires via each one of its three states. Similarly, one might want all sorts of logic gates, like a not-gadget, an or-gadget, an xor-gadget etc; where you can have some sort of constraint via the gadget that relates 2 or 3 wires in such a way.

A Building-block

• First, let's reserve a number, for example, $\mathbf 1$, on the board. We will make $\mathbf 1$ a building block for everything else.
• We will use a corner to make sure that $\mathbf 1$ can never connect to another $\mathbf 1$, except in this corner, where it must.
• Below (in the three figures) is the corner, and how we place the $\mathbf 1$s there.
• We will use the $\star$ to indicate unique values in all the grid, in all the diagrams.
• In fact, we will cover our grid with $\star$ values before overlaying them with important values; therefore, by default cover everything with $\star$ values.

As you can see, by placing the $3$   $\mathbf{1}$s the pair $\mathbf{(1,1)}$ must be used up in this configuration; it must use one of the dashed-tiles. Now $\mathbf{(1,1)}$ can never happen elsewhere in the board, which is what we need.

There are alternate ways of reserving a number, either against the wall with $4$ of them, or in the middle of nowhere, with $5$ of them in a cross. Any way is fine, as long as $\mathbf{(1,1)}$ is forced.

A Wall

Now, it would be very useful to be able to make "walls" and "corners" all over the place, not just at the sides of the grid. Look what happens if we line up pairs of ones in a line; the one's have no choice but to pair with their neighbors, making a "wall" of width $4$.

Images below, from left to right:

1. A line of pairs of $\mathbf 1$s.
2. The only possible tiling of that $\mathbf 1$-square.
3. The only possible tiling of (almost) all the $\mathbf 1$s in the line.
4. The wall line, drawn for emphasis.

An initial attempt at a wire

Now, by placing two "walls" opposite each-other, and leaving a space of $\mathbf 1$ between the walls, perhaps we can come up with a "wire"-like gadget.

Showing only the wall-borders, this is what we get in the figures below (left to right):

• Placing two walls opposite each-other.
• Putting unique numbers inside.
• Rightmost two: Two possible states of the wire.

How it works:

There cannot be any holes in the tube/wire, therefore, if the the tiles are shifted up, then they all must be shifted up, all along the tube; if they are shifted down, it will "suck" down all of them. Thus, we can send a "signal" from one side of the wire to the other; in other words, propagate a value.

Thus, now we can propagate a value across long distances!

Remaining limitations are:

• We cannot bend a wire,
• We cannot split a wire,
• We cannot cross wires,
• We might have annoying layout issues because we must be careful about wire-length parity.

Bending a Wire, Part 1: Wall Below

Next problem is, we need to be able to bend a wire, not just go straight ...

So. We will break the bending part down into two parts; the upper part and the lower part. First the lower part. Ignore the upper part of the bend, we will do that later.

The figures below show a bit of a problem with bending; the top of the wire is "loose", it seems difficult to make a wall that turns a sharp 90 degrees.

Left to right:

• The top of a wire is "loose".
• What happens if we try to bend it; we want to wire to be in between the blue lines. Again, Ignore the upper part of the bend, we will do that later.
• As you can see, the top $\mathbf 1$s are loose, they can tile along the wall, or through the wire! This is no good.

One solution is as follows:

• Pick a $\mathbf{(x,1)}$ pair near the bend. Take the value of that $\mathbf x$ square, let us name it $\mathbf{ q \star}$; this means the number is unique in the entire grid, just like $\mathbf \star$, and is reused once, here in this bend only. Because this $\mathbf x$ is paired with a $\mathbf 1$, it cannot be paired with a $\mathbf 1$ again. Therefore, we place it right on top of the rightmost-topmost $\mathbf 1$. Now, we can clearly see, the only option remaining to pair for that $\mathbf 1$ is to its right, and thus it will solidify the wall.

Illustration below, description from left to right:

• The situation with the problem.
• Pick a square, let $\mathbf{q \star}$ be the square value of any square in the bend (of course not $\mathbf 1$s though).
• The two togglings of the rightmost-topmost $\mathbf 1$ tilings; this time, only one of them is valid.

However, how can we be sure this $\mathbf {{q}{\star}}$ won't ruin the wire? Below you can see the states of the wire, and that the $\mathbf {{q}{\star}}$ will not hamper with it.

From left to right:

• The current construction.
• Two rightmost figures: The states of the wire; empirically, they are not hampered by the introduction of $\mathbf {{q}{\star}}$.

Now we still have a loose $\mathbf 1$ on top; the leftmost-topmost-$\mathbf 1$.

We will do the same thing; pick a pair $\mathbf{({r}{\star},1)}$ that is already paired in the bend-tiles, and place $\mathbf{r}{\star}$ on top of the leftmost-topmost-$\mathbf 1$.

Illustration below, left to right:

• Our current construction.
• The problem: leftmost-topmost-$\mathbf 1$ can pair with a number in the wire, or with the wall; we want it to only pair with the wall.
• Choosing an $\mathbf{r}{\star}$, and using the same number on top of the leftmost-topmost-$\mathbf 1$.

And we finally get our lower bend. Illustration below, descriptions, from left to right:

• Left: Our final construction for a bend.
• Right: How to continue the wire to the left.

Bending a Wire, Part 2: Wall Above

The walls to make the top corner of the bend are much simpler. You simple align a vertical wall with a horizontal wall. Illustration below, description from left to right:

• The wire-bend we want to make.
• Place the vertical section of the wall squares down.
• Tiling the squares of the vertical-wall.
• Placement and tiling of the horizontal wall; it can meet the vertical wall, and form a corner.

Now you should be convinced that we can place and bend wires. We still can't split or cross wires though, more on that later.

Remaining limitations are:

• We cannot bend a wire,
• We cannot split a wire,
• We cannot cross wires,
• We might have annoying layout issues because we must be careful about wire-length parity.

A Valued Wire

Now we have wires, it would be nice to have a valued-wire, where we can see the value of a wire, like an LED on a circuit board. So what we do, is take a wire, say of length $7$, and introduced a named $\star$ square, we'll call it ${\mathcal T}{\star}$, and another named square, we'll call it ${\mathcal F}{\star}$. These are both unique to each valued wire section, ie. only twice, and they will only get reused within a single valued wire. They are placed in pairs, the two ${\mathcal T}{\star}$ squares right next to each-other, and the two ${\mathcal F}{\star}$ squares next to each-other, with a single $\star$ square separating them. Illustrated below, description from left to right:

• Left: A wire.
• Right: The square-configuration.

So how do we tell if a wire is true or false? Well, a wire has two states. In each of these states, one of ${\mathcal T}{\star}$ or ${\mathcal F}{\star}$ will be paired in the same tile; the value that is paired is the value of the wire. Illustration below, desciption from left to right:

• Left, right: The two states of the valued wire;
• Left: Wire is valued trued, as the ${\mathcal T}{\star}$ squares share a single tile
• Right: Wire is valued false as the ${\mathcal F}{\star}$ squares share a single tile.

We can now have named variable that we can use, to place our ${\rm 3\text{-}S{\small AT}}$ variables down on the grid. We can connect two valued wires and force them to have the same value, or if we connect them with an odd-length, force them to have different values; and using wires, we can do this long-distance, across the grid. Using wires, we can propagate the values of the named variables all over the place.

Remaining limitations are:

• We cannot split a wire,
• We cannot cross wires,
• We might have annoying layout issues because we must be careful about wire-length parity.

Not-gate

A not-gate is unnecessary as it is implicit: simply using an off-by-one wire length we can negate the value of the wire.

A Clause Gate

Now I can demonstrate a simple clause gadget; it will connect to $3$ wires, and force one of them to be "pulled" state, and force the other two to be in the "pushed" state. We can use this, this is an exactly one-in-three relationship; we set the odd-wire-state to mean "true", and the other two wire-states to mean "false", and we are set.

Illustrations below, descriptions from left to right:

• The wire-layout of the clause gadget. It makes a "plus" sign; the joining of 3 wires in one spot.
• Fill the wire with unique $\star$ squares.
• The three states of the center square. Each of these states "pulls" exactly one wire into the center, the essential point of the gate; to act like a ${\rm 1\text{-in-}3\text{-}S{\small AT}}$ clause.

Now let's take a look at the different states. Illustration below, description from left to right:

• The left wire is pulled into the center; the other two are pushed out.
• The bottom wire is pulled into the center; the other two are pushed out.
• The bottom-right wire is pulled into the center; the other two are pushed out.

Now, if you attach wires with the right length-parity (even or odd length) to the end of this gate, only one of them could be true, the other two false (depending if you attach them oddly, you can generalize this a bit). Thus we can connect $3$ values into a $1\text{-in-}3$ CNF clause.

Remaining limitations are:

• We cannot split a wire,
• We cannot cross wires,
• We might have annoying layout issues because we must be careful about wire-length parity.

Splitting a Wire

To split a wire, we first line up two wires next to each-other. Next, as a visual aid, we label each of the wires with two ${\mathcal T}{\star}$ squares, one next to the other. This will allow us to see when the wire is "true": when the two ${\mathcal T}{\star}$ squares of a wire in a single tile, then it will be true, otherwise false. Each wire should get its own pair of ${\mathcal T}{\star}$ pairs, so we'll name one pair ${\mathcal T}_1{\star}$ and the other ${\mathcal T_2}{\star}$. Then we introduce three new named-unique $\star$ values, $a{\star},b{\star},c{\star}$. We will place these three next to each-other, once on each wire. However, on one wire, keep a single $\star$ squares between the $a{\star},b{\star},c{\star}$ squares and the ${\mathcal T}{\star}$ pair. On the other wire, put two $\star$ squares between the $a{\star},b{\star},c{\star}$ squares.

Illustration below, description from left to right:

• Wire layout. Note the walls are a bit thick, so the wires are drawn closer together for illustration purposes; in reality, they are a bit farther apart.
• The square-values; the ${\mathcal T}{\star}$ values on top, and the split-connectors $a{\star},b{\star},c{\star}$ beneath.

What this does is force the wires not to be different; if $a{\star},b{\star}$ is tiled on one wire, then the second wire cannot be off-by-one, because then that would imply $a{\star},b{\star}$ is tiled on the second wire, and thus $a{\star},b{\star}$ would be tiled twice. Illustration below, description from left to right:

• Example state of the left wire, valued as true.
• Bad state of the second wire; it tries to be differently valued, but then it gets a duplicate pair.
• Good state of the second wire, now they are the same value, and there are no duplicate pairs.

If you play around with the other two possible states, you will see this extends to those as well, and it works both ways. Thus these two wires are now the same; we have successfully split a wire. We can split the wire as many times as we like, each time using a new set of $a{\star},b{\star},c{\star}$.

Remaining limitations are:

• We cannot split a wire,
• We cannot cross wires,
• We might have annoying layout issues because we must be careful about wire-length parity.

A Cordless Wire!

Well, to my delight, splitting a wire turned out to be cordless! That is, in the illustrations above, I lay the wires next to each-other, but there is no reason to! We can place the wires anywhere on the grid, and they'd still be "entangled" so-to-speak. This saves us a lot of trouble:

• We don't even have to worry about crossing wires. This lets us reduce from non-planar variants of ${\rm\mathbf{3\text{-} S{\small AT}}}$
• We have to do any annoying layout, getting the wires to their locations, it is easy! Like a cordless phone! Freedom!
• We don't have to worry about wire-length parity/off-by-one layout.
• We can make pretty minimally sized reduction; the variables will each get a single set of long wire strips, with a lot of cordless connections along the wires. These connections will be to clause-gates, which will reside in its own location on the grid. The clause will now only consist of the clause gadget and three cordless wires sticking out of it.

Remaining limitations are:

• We cannot cross wires,
• We might have annoying layout issues because we must be careful about wire-length parity.

The Reduction, first attempt

Let $\Phi(\mathbf x)= \bigwedge_i C_i$ be a $1\text{-in-}3\text{-}{\rm S{\small AT}}$ boolean formula.

• For each $x_j \in \mathbf x$, lay-out a single long wire, in rows, near the bottom of the grid.
• For each $C_i \in \Phi(\mathbf x)$, make a clause-gate at the top of the grid; you can lay them out however you like; best fill it up in a square area, but you can lay it out in a single long row as well.
• For each $x_j$ variable participating in a clause $C_i$, place a cordless-wire at one of the $3$ wire-pins of the clause gate; place the other $a{\star},b{\star},c{\star}$ of each connection onto the corresponding variable wire/row. Negated terms should just place the cordless connection to the clause a distance of one farther away, changing the wire-length-parity, and negating the value.

What it might look like:

• Figure: A clause, directly connected to cordless wires. "Hotspots" are the way we symbolize the $a{\star},b{\star},c{\star}$ from here on. These hotpots will each be connected to the variables in the grid.

And here is what the grid might look like:

• Figure: The resulting game-board. The variables are lined up in rows on the bottom. The clauses are spread out across the top. This layout gives quadratic blowup; a smarter layout can avoid quadratic blowup.

Last Minute Details

Recall the decision problem:

Is there a perfect tiling covering a given a $(n+1) \times (n+2)$ grid with $n$ unique tiles?

So for an $(n+1) \times (n+2)$ grid, we can only use $n$ variables. But our reduction requires a lot of unique variables, much more than $\mathcal O(n)$. There are several ways to solve this issue.

• One way, is to square the size of the grid in both axes. So now our $\mathcal O\left(|\mathbf x|\times \left|\Phi(\mathbf x)\right|\right)$ grid is merely $\in \mathcal O\left(n\right)$, which means all of our unique numbers can be bounded by $n$. Then, we must fill up the rest of the grid, reusing our unique numbers, but being very careful not to place any numbers that our adjacent to each-other in our grid, adjacent to each-other in the filler-space of the rest of the grid. There are several creative ways to do this, I'll leave that as an exercise. This method induces an additional quadratic blowup, obviously.
• Another, more succinct, more complex way, is to diversify the $\mathbf 1$ block. Instead of just one building block, we can use $\mathcal O(n)$ building blocks, and then we can reuse the numbers they pair with. This method allows us to avoid quadtratic blowup.

---

Graph sources

• Dominosa.Part.I.tex (writelatex)
• Dominosa.Part.II.tex (writelatex)
• Dominosa.Part.III.tex (writelatex)
• Dominosa.Part.IV.tex (writelatex)