patternMajor
Is Dominosa NP-Hard?
Viewed 0 times
harddominosastackoverflow
Problem
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?
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?
Solution
${\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{\
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{\
Context
StackExchange Computer Science Q#16850, answer score: 22
Revisions (0)
No revisions yet.