Instantly share code, notes, and snippets.

realazthat/Dominosa.Part.I.tex Last active Dec 28, 2015

Feel free to use any of this code as you wish, under the MIT license, copyright Azriel Fasten.

##${\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}$$

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.

###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

 \documentclass[tikz,margin=5em]{standalone} \usepackage{intcalc,calc} \usepackage{tikz} \usepackage{verbatim} \usepackage{amsmath,amssymb} \usetikzlibrary{arrows} \usetikzlibrary{decorations.pathreplacing} \usepackage{relsize} \usetikzlibrary{shapes} \usetikzlibrary{fadings} \title{Dominosa.V} \begin{document} \def\tilecolor{gray} \def\squarecolor{gray!40!white} \tikzset{dstyle/.style={line width=0.5 mm,rounded corners,fill=gray,fill opacity=.3}} \tikzset{snode/.style={rounded corners,fill=\squarecolor, text opacity=1,fill opacity=1, minimum size=1 cm,font=\bfseries}} \tikzset{wline/.style={rounded corners,line width=1mm,color=blue!40!black}} \tikzset{bline/.style={rounded corners,line width=.5mm,color=black}} \tikzset{brect/.style={fill=black}} \tikzset{darrow/.style={-stealth,line width=.5mm}} \tikzset{idarrow/.style={stealth-,line width=.5mm}} \tikzset{gstyle/.style={step=1cm,black,line width=.1mm,opacity=.3}} \tikzset{checknode/.style = {font=\relsize{#1}}} \tikzset{descarrow/.style={-,line width=1mm,orange}} \tikzset{descnode/.style={ellipse,fill=green!20,fill opacity=0.7}} \def\tilemargin{.05} \def\kleene{${\star}$} \def\numeralA{$\mathbf{1}$} \def\qkle