Matrix Coloring under Vertical and Horizontal Constraints 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}$.
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* -&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


The vertical rules are:

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


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.