<p><strong>A1)</strong> The problem remains NP-complete even for fixed $|\Sigma|=3$</p>

<p>A reduction from planar 1-3-SAT is the following; suppose $\Sigma = \{0,1,2\}$</p>

<ul>
<li>use a sequence of $M_{ij} = \{0,1\}$ <em>pairs</em> of horizontal/vertical cells as "wire" gadgets to "carry" the truth values ($0=true$, $1,2 = false$) of the variables (the horizontal and vertical rules of the wires forbid switching between $true \leftrightarrow false$)</li>
<li>the beginning of a wire acts as "variable assignment"</li>
<li>the clauses are simulated using a circular pattern in which the horizontal and vertical rules force a sequence of $012\;012....$ along the circuit</li>
<li>each clause has 3 incoming wires; the wires are arranged to "touch" the circuit in three distinct places <em>modulo 3</em>; in this way only one of the three wires can have the value of true.</li>
</ul>

<p>The following figure should be self-explanatory.</p>

<p><a href="https://i.sstatic.net/LEuLQ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/LEuLQ.png" alt="enter image description here"></a></p>

<p>If instead of "local" horizontal/vertical rules you want to use "global" rules (a set of rules that are common to all cells) then you must add another extra "blank" color to "isolate" the wires and the reduction above still holds.</p>

<p>With $|\Sigma| = 2$ the problem is polynomial time solvable (each cell is represented with a binary variable, and the rules can be expressed with a 2-SAT formula).</p>

<p><strong>A2)</strong> The game is also very similar to a "relaxed" version of the game <a href="http://www.binarypuzzle.com/" rel="nofollow noreferrer">Binary Puzzle</a>: a puzzle game played on a $n \times n$ grid. Intially some of the cells contain a zero or a one; the aim of the game is to fill the empty cells according to the following rules:</p>

<ol>
<li>Each cell should contain a zero or a one and no more than two similar numbers next to or below each other are allowed</li>
<li>Each row and each column should contain an equal number of zeros and ones</li>
<li>Each row is unique and each column is unique</li>
</ol>

<p>Using a set of <em>eight colors</em> you can "simulate" the rule #1 of binary puzzle (which is NPC even without rules #2 and #3 ). This is a quick idea for a reduction.</p>

<p>Each one of the eight colors has 3 bits $b_0b_1b_2$;</p>

<ul>
<li>bit 0 $b_0$ represents the $0$ or $1$ of the binary puzzle grid</li>
<li>bit 1 $b_1$ is $1$ if and only if the cell on the left has the same color</li>
<li>bit 2 $b_2$ is $1$ if and only if the cell above has the same color</li>
</ul>

<p>If a cell $i,j$ of the initial board of binary puzzle is empty then you set $M_{ij} = \Sigma$</p>

<p>If a cell $i,j$ of the initial board of binary puzzle is a forced $1$ then you set $M_{ij} = \{ 1** \}$ (100,101,110,111)</p>

<p>If a cell $i,j$ of the initial board of binary puzzle is a forced $0$ then you set $M_{ij} = \{ 0** \}$ (000,001,010,011)</p>

<p>The horizontal rules are:</p>

<pre><code>00* -&gt; 01*  : allow another 0 on the right only if the previous was 1
0** -&gt; 1**  : always allow a 0-&gt;1 transition
10* -&gt; 11*  : allow another 1 on the right only if the previous was 0
1** -&gt; 0**  : always allow a 1-&gt;0 transition
</code></pre>

<p>The vertical rules are:</p>

<pre><code>0*0 -&gt; 0*1  : allow another 0 below only if the above one was 1
0** -&gt; 1**  : always allow a 0-&gt;1 transition
1*0 -&gt; 1*1  : allow another 1 below only if the above one was 0
1** -&gt; 0**  : always allow a 1-&gt;0 transition
</code></pre>

<p>You can find the <a href="http://www.nearly42.org/cstheory/binary-puzzle-np-complete/" rel="nofollow noreferrer">proof of NP-completeness of binary puzzle</a> on my blog (soon or later I'll find the time to submit it somewhere).</p>

<p><strong>A3)</strong> Furthermore <em>if you add the constraint that each color can be used only once</em>, then the problem is still NPC even on $n \times 1$ grids with only horizontal constraints. </p>

<p>The reduction is from 3-PARTITION which is strongly NPC: given a set $X = \{x_1, ..., x_{3q}\}$ and a target sum $B = (\sum x_i)/3$; use (new) colors $c^i_1,...,c^i_i$ for each $x_i$. Start with a grid $G$ of length $Bq+q + 1$ with  the following sets of allowed colors:</p>

<p>$S E^B T_1 E^B T...E^B T_q$</p>

<p>Where</p>

<ul>
<li>$S$ (the set $M_1$) represents the starting color $\{ c_S \}$ </li>
<li>$T_i$ represents a <em>breaking</em> block that contain $q$ special colors $\{ c_{Ti} \}$</li>
<li>$E^B$ is a sequence of $B$ "blocks" that can contain any color from $\Sigma \setminus \{ c_S, c_{Ti}\}$</li>
</ul>

<p>The horizontal constraints are:</p>

<ul>
<li>$(S,c^i_1)$ for $i = 1...n$: that allows to start from $S$ and start using a color sequence from $c^i$</li>
<li>$(c^i_j, c^i_{j+1})$ for $j = 1...i-1$: that forces the complete color sequence of each $c^i$ (once started)</li>
<li>$(c^i_i, c^j_1)$ for $i \neq j$ that allows to start another color sequence once ended the previous one</li>
<li>$(c^i_i, c_{Tj})$ for $i = 1...n, j=1..q-1$: that "align" the color sequences to the break blocks (that guarantee that the "unary" sum is equal to $B$)</li>
<li>$(c_{Tj}, c^i_1, )$ for $i = 1...n, j=1..q-1$: that allows another color sequence after a breaking block $T_j$</li>
</ul>

<p>The $n \times 1$ grid $G$ can be properly colored if and only if the original 3-PARTITION problem has a solution.</p>

<p>This is an example: given the 3-PARTITION instance:</p>

<p>$A = \{ 3,3,2,2,2,2 \}\; (B=7, q=2)$</p>

<p>We can use $2B + 2$ distinct colors and build a coloring game instance on a $2B + 2 + 1 = 17 \times 1$ grid like in the figure.</p>

<p><a href="https://i.sstatic.net/fQXXh.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/fQXXh.png" alt="enter image description here"></a></p>

CC BY-SA 3.0
2017-11-28T19:58:17.043Z
thanks for the comments! For the 1xn case I fail to see why it is NP complete. Reduction to directed reachability: Create vertices $v(a,x,y)$  for each $a \in [n-1]$, each color  $x \in M_{1a}$ and $y\in M_{1(a+1)}$ such that $(x,y)\in H_{1a}$.  Now connect a vertex $v(a,x, y)$ to $v(a+1,z,w)$ if and only if $y=z$. Then add a source vertex $s$ connected to all vertices $v(1,x,y)$ and a target vertex $t$ connected to all vertices $v(n-1,x,y)$. We have a solution if and only if there is a directed path from $s$ to $t$. The size of the graph is polynomial in $|\Sigma|$.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2017-11-28T20:46:17.693Z
@MateusdeOliveiraOliveira: I'll add a "colorful" example of the $n \times 1$ case tomorrow!
Marzio De Biasi
CC BY-SA 3.0
2017-11-28T21:57:43.490Z
@MarzioDeBiazi, in the graph constructed in my previous comment, there is a path $s,v(1,x_1,x_2)v(2,x_2,x_3)...v(n-1,x_n-1,x_n), t$ if and only if $x_1x_2...x_n$ is a $1xn$ matrix with $x_j\in M_{1j}$ for each $j\in [n]$ and $(x_j,x_{j+1})\in H_{1j}$ for each $j\in [n-1]$. Therefore, either you're claiming that $NP = NL$ or we are speaking about distinct problems. Note that I'm writing $1xn$ matrix to denote a matrix with $1$ row and $n$ columns. And that the set of colors $\Sigma$ is given as a list in the input, and in particular I'm assuming that $\Sigma = n^{O(1)}$.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2017-11-29T07:42:20.060Z
@MateusdeOliveiraOliveira: you are right: while drawing the example for the nx1 case I found that, in order to be NP-complete, you must also add the constraint that each color is used only once (and the problem becomes less interesting).
Marzio De Biasi
CC BY-SA 3.0
2017-12-01T08:16:26.687Z
@MateusdeOliveiraOliveira: if you are interested I also found a proof that your problem is NPC even with fixed 4 colors ($|\Sigma| = 4$)
Marzio De Biasi
CC BY-SA 3.0
2017-12-01T08:36:44.073Z
@MarzioDeBiazi actually I'm interested in the proof in the case of 4 colors. Even more if one can push the barrier to 3 or 2 colors.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2017-12-03T17:39:41.643Z
@MateusdeOliveiraOliveira : for 2 colors, isn't it in P by reducing to 2SAT? You have one boolean variable $x_{i,j}$ per entry in your matrix. $M_{i,j}$ constraints are either trivial or fix the value of $x_{i,j}$. $V_{i,j}$ constraints only mention $x_{i,j}$ and $x_{i+1,j}$ and can thus be encoded as 2CNF. Same with $H_{i,j}$.
holf
CC BY-SA 3.0
2017-12-03T21:45:30.147Z
@holf you're right. The fact that the problem is in P for two colors was also pointed by MarzioDeBiasi in his answer. So it seems that the only case left for NP-hardness is 3 colors.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2017-12-03T22:21:38.833Z
@MateusdeOliveiraOliveira oh right, thanks, I missed it in Marzio's answer as I only skimmed it, my bad.
holf
CC BY-SA 3.0
2017-12-04T15:20:42.870Z
@MateusdeOliveiraOliveira: I think I found a reduction for $| \Sigma | = 3$; let me know if you need further details.
Marzio De Biasi
CC BY-SA 3.0
2017-11-28T18:46:35.683Z
2017-12-04T18:09:08.610Z
2017-12-04T18:09:08.610Z
Marzio De Biasi
<p>I'm searching for the correct name of the following NP-complete problem. I  would also appreciate answers pointing to problems with similar-looking variations. </p>

<p>The input consists of </p>

<ul>
<li>A set of colors $\Sigma$ with $|\Sigma|=n^{O(1)}$.</li>
<li>An $nxn$ square matrix $M$ where each entry $M_{ij}$ is a subset of $\Sigma$</li>
<li>For each $i\in [n]$ and each $j\in [n-1]$, a set $H_{ij}\subseteq \Sigma\times \Sigma$ of horizontal constraints.</li>
<li>For each $i\in [n-1]$ and each $j\in [n]$, a set $V_{ij}\subseteq \Sigma\times \Sigma$ of vertical constraints. </li>
</ul>

<p>A solution for the problem is an $n\times n$ matrix $N$ where each entry $N_{ij}$ belongs to $M_{ij}$, each pair horizontally consecutive entries $(N_{ij},N_{i(j+1)})$ belongs to $H_{ij}$ and each pair of vertically consecutive entries $(N_{ij},N_{(i+1)j})$ belongs to $V_{ij}$. </p>

<reference-request><np-hardness><np-complete><board-games>
Matrix Coloring under Vertical and Horizontal Constraints
Mateus de Oliveira Oliveira
# Matrix Coloring under Vertical and Horizontal Constraints

(Asked by: username_0 on 2017-11-28)

I'm searching for the correct name of the following NP-complete problem. I would also appreciate answers pointing to problems with similar-looking variations.

The input consists of

* A set of colors $\Sigma$ with $|\Sigma|=n^{O(1)}$.
* An $nxn$ square matrix $M$ where each entry $M\_{ij}$ is a subset of $\Sigma$
* For each $i\in [n]$ and each $j\in [n-1]$, a set $H\_{ij}\subseteq \Sigma\times \Sigma$ of horizontal constraints.
* For each $i\in [n-1]$ and each $j\in [n]$, a set $V\_{ij}\subseteq \Sigma\times \Sigma$ of vertical constraints.

A solution for the problem is an $n\times n$ matrix $N$ where each entry $N\_{ij}$ belongs to $M\_{ij}$, each pair horizontally consecutive entries $(N\_{ij},N\_{i(j+1)})$ belongs to $H\_{ij}$ and each pair of vertically consecutive entries $(N\_{ij},N\_{(i+1)j})$ belongs to $V\_{ij}$.

**Tags:** reference-request, np-hardness, np-complete, board-games

---

## 1 answers

### Answer by username_1 on 2017-11-28. Score: 3 | Accepted answer

A1) The problem remains NP-complete even for fixed $|\Sigma|=3$
A reduction from planar 1-3-SAT is the following; suppose $\Sigma = \{0,1,2\}$

use a sequence of $M_{ij} = \{0,1\}$ pairs of horizontal/vertical cells as "wire" gadgets to "carry" the truth values ($0=true$, $1,2 = false$) of the variables (the horizontal and vertical rules of the wires forbid switching between $true \leftrightarrow false$)
the beginning of a wire acts as "variable assignment"
the clauses are simulated using a circular pattern in which the horizontal and vertical rules force a sequence of $012\;012....$ along the circuit
each clause has 3 incoming wires; the wires are arranged to "touch" the circuit in three distinct places modulo 3; in this way only one of the three wires can have the value of true.

The following figure should be self-explanatory.

If instead of "local" horizontal/vertical rules you want to use "global" rules (a set of rules that are common to all cells) then you must add another extra "blank" color to "isolate" the wires and the reduction above still holds.
With $|\Sigma| = 2$ the problem is polynomial time solvable (each cell is represented with a binary variable, and the rules can be expressed with a 2-SAT formula).
A2) The game is also very similar to a "relaxed" version of the game Binary Puzzle: a puzzle game played on a $n \times n$ grid. Intially some of the cells contain a zero or a one; the aim of the game is to fill the empty cells according to the following rules:

Each cell should contain a zero or a one and no more than two similar numbers next to or below each other are allowed
Each row and each column should contain an equal number of zeros and ones
Each row is unique and each column is unique

Using a set of eight colors you can "simulate" the rule #1 of binary puzzle (which is NPC even without rules #2 and #3 ). This is a quick idea for a reduction.
Each one of the eight colors has 3 bits $b_0b_1b_2$;

bit 0 $b_0$ represents the $0$ or $1$ of the binary puzzle grid
bit 1 $b_1$ is $1$ if and only if the cell on the left has the same color
bit 2 $b_2$ is $1$ if and only if the cell above has the same color

If a cell $i,j$ of the initial board of binary puzzle is empty then you set $M_{ij} = \Sigma$
If a cell $i,j$ of the initial board of binary puzzle is a forced $1$ then you set $M_{ij} = \{ 1** \}$ (100,101,110,111)
If a cell $i,j$ of the initial board of binary puzzle is a forced $0$ then you set $M_{ij} = \{ 0** \}$ (000,001,010,011)
The horizontal rules are:
00* -> 01*  : allow another 0 on the right only if the previous was 1
0** -> 1**  : always allow a 0->1 transition
10* -> 11*  : allow another 1 on the right only if the previous was 0
1** -> 0**  : always allow a 1->0 transition

The vertical rules are:
0*0 -> 0*1  : allow another 0 below only if the above one was 1
0** -> 1**  : always allow a 0->1 transition
1*0 -> 1*1  : allow another 1 below only if the above one was 0
1** -> 0**  : always allow a 1->0 transition

You can find the proof of NP-completeness of binary puzzle on my blog (soon or later I'll find the time to submit it somewhere).
A3) Furthermore if you add the constraint that each color can be used only once, then the problem is still NPC even on $n \times 1$ grids with only horizontal constraints. 
The reduction is from 3-PARTITION which is strongly NPC: given a set $X = \{x_1, ..., x_{3q}\}$ and a target sum $B = (\sum x_i)/3$; use (new) colors $c^i_1,...,c^i_i$ for each $x_i$. Start with a grid $G$ of length $Bq+q + 1$ with  the following sets of allowed colors:
$S E^B T_1 E^B T...E^B T_q$
Where

$S$ (the set $M_1$) represents the starting color $\{ c_S \}$ 
$T_i$ represents a breaking block that contain $q$ special colors $\{ c_{Ti} \}$
$E^B$ is a sequence of $B$ "blocks" that can contain any color from $\Sigma \setminus \{ c_S, c_{Ti}\}$

The horizontal constraints are:

$(S,c^i_1)$ for $i = 1...n$: that allows to start from $S$ and start using a color sequence from $c^i$
$(c^i_j, c^i_{j+1})$ for $j = 1...i-1$: that forces the complete color sequence of each $c^i$ (once started)
$(c^i_i, c^j_1)$ for $i \neq j$ that allows to start another color sequence once ended the previous one
$(c^i_i, c_{Tj})$ for $i = 1...n, j=1..q-1$: that "align" the color sequences to the break blocks (that guarantee that the "unary" sum is equal to $B$)
$(c_{Tj}, c^i_1, )$ for $i = 1...n, j=1..q-1$: that allows another color sequence after a breaking block $T_j$

The $n \times 1$ grid $G$ can be properly colored if and only if the original 3-PARTITION problem has a solution.
This is an example: given the 3-PARTITION instance:
$A = \{ 3,3,2,2,2,2 \}\; (B=7, q=2)$
We can use $2B + 2$ distinct colors and build a coloring game instance on a $2B + 2 + 1 = 17 \times 1$ grid like in the figure.

> **Comments:**
> **username_0**: thanks for the comments! For the 1xn case I fail to see why it is NP complete. Reduction to directed reachability: Create vertices $v(a,x,y)$  for each $a \in [n-1]$, each color  $x \in M_{1a}$ and $y\in M_{1(a+1)}$ such that $(x,y)\in H_{1a}$.  Now connect a vertex $v(a,x, y)$ to $v(a+1,z,w)$ if and only if $y=z$. Then add a source vertex $s$ connected to all vertices $v(1,x,y)$ and a target vertex $t$ connected to all vertices $v(n-1,x,y)$. We have a solution if and only if there is a directed path from $s$ to $t$. The size of the graph is polynomial in $|\Sigma|$.  
> **username_1**: @MateusdeOliveiraOliveira: I'll add a "colorful" example of the $n \times 1$ case tomorrow!  
> **username_0**: @MarzioDeBiazi, in the graph constructed in my previous comment, there is a path $s,v(1,x_1,x_2)v(2,x_2,x_3)...v(n-1,x_n-1,x_n), t$ if and only if $x_1x_2...x_n$ is a $1xn$ matrix with $x_j\in M_{1j}$ for each $j\in [n]$ and $(x_j,x_{j+1})\in H_{1j}$ for each $j\in [n-1]$. Therefore, either you're claiming that $NP = NL$ or we are speaking about distinct problems. Note that I'm writing $1xn$ matrix to denote a matrix with $1$ row and $n$ columns. And that the set of colors $\Sigma$ is given as a list in the input, and in particular I'm assuming that $\Sigma = n^{O(1)}$.  
> **username_1**: @MateusdeOliveiraOliveira: you are right: while drawing the example for the nx1 case I found that, in order to be NP-complete, you must also add the constraint that each color is used only once (and the problem becomes less interesting).  
> **username_1**: @MateusdeOliveiraOliveira: if you are interested I also found a proof that your problem is NPC even with fixed 4 colors ($|\Sigma| = 4$)  
> **username_0**: @MarzioDeBiazi actually I'm interested in the proof in the case of 4 colors. Even more if one can push the barrier to 3 or 2 colors.  
> **username_2**: @MateusdeOliveiraOliveira : for 2 colors, isn't it in P by reducing to 2SAT? You have one boolean variable $x_{i,j}$ per entry in your matrix. $M_{i,j}$ constraints are either trivial or fix the value of $x_{i,j}$. $V_{i,j}$ constraints only mention $x_{i,j}$ and $x_{i+1,j}$ and can thus be encoded as 2CNF. Same with $H_{i,j}$.  
> **username_0**: @holf you're right. The fact that the problem is in P for two colors was also pointed by MarzioDeBiasi in his answer. So it seems that the only case left for NP-hardness is 3 colors.  
> **username_2**: @MateusdeOliveiraOliveira oh right, thanks, I missed it in Marzio's answer as I only skimmed it, my bad.  
> **username_1**: @MateusdeOliveiraOliveira: I think I found a reduction for $| \Sigma | = 3$; let me know if you need further details.  

---

