Prove TILING is NP-Complete

I have a homework task to show that $\mathrm{TILING} = \{(T, 1^N) \mid \text{it is possible to cover } N \times N \text{ square with tiles from }T\}$, where $t\in T$ is $C^4$ for some color set $C$, is NP-complete.

It is not hard to show that $\mathrm{TILING}$ is in NP.

How can I show that it is NP-Hard? Can I reduce some known language ($\mathrm{SAT}$, $\mathrm{3COL}$, $\mathrm{CLIQUE}$, etc) to it?

I have some idea of solution, similar to the proof of Cook-Levin theorem (to encode state of the Turing Machine), but it seems awkward to do it, since I have proved NP-Completeness of $\mathrm{SAT}$.

UPDATE:

• A "color set" is just some set, e. g. {6, 13, 42}, {1, 2, 3, ..., 200}, then a tile can look like (6, 6, 6, 13), (6, 13, 42, 6) for the first and (1, 2, 3, 4), (8, 8, 8, 8) for the second.

• Every neighbor side (order: up, left, down, right) must have the same color, but no restrictions for "outer" sides (edges), which doesn't have neighbors. And it's not possible to rotate tiles.

Instead of $\mathsf{TILING}$, I proved that $\mathsf{RectangleTILING}$ is $\mathsf{NP}$-complete by finding a reduction from $\mathsf{3SAT}$.

Problem $\mathsf{RectangleTILING}$:

• Input: a set $T$ of tiles, two dimensions $M$ and $N$ (in binary or unary, it doesn't matter);

• Question: is it possible to cover a rectangle of size $N\times M$ with tiles of $T$?

If necessary, I will add some details to prove that $\mathsf{RectangleTILING}\leqslant_m^p\mathsf{TILING}$, but I think it is not that hard to prove.

I consider a 3-CNF boolean formula $\varphi = \bigwedge\limits_{i=0}^{m-1} C_i$ where $\forall i \in [\![0,m-1]\!]$, $C_i = (\ell_{i1}\vee \ell_{i2}\vee\ell_{i3})$ and $\ell_{ij}$ is either $x$ or $\overline{x}$ with $x\in\mathcal{V} = \{x_0,…,x_{n-1}\}$. I construct an input $(T, 3m, 2n)$ of $\mathsf{RectangleTILING}$ such that $\varphi$ is satisfiable if and only if it is possible to cover a rectangle of size $2n\times 3m$ with tiles of $T$.

Note that it is possible to encode coordinates for tiles using the colors. For example, the following tile could be put only on column $c$ and row $r$.

It is also possible to encode multiple informations in colors, using tuples. For readability purposes, I will chose to write tiles coordinates outside of colors.

Each tile will have only one choice of coordinates in the rectangle.

Now the idea is to use two rows per variable:

• one row per variable $x_j$ will keep track of the boolean assignment chosen for $x_j$;

• the other row will permit to know which variable satisfies each clause;

and three columns per clause:

• one column per clause will sum up the boolean assignment of each variable;

• one column will chose a variable to satisfy the clause;

• the last column will pick a clause tile.

In details:

• for $i$ from $0$ to $m-1$:

• for $j$ from $0$ to $n-1$:

-
in coordinates $(2j, 3i)$, two possible tiles, encoding $x_j$ or $\overline{x_j}$:

-
in coordinates $(2j, 3i+1)$:

• for $k$ from $0$ to $n-1$, four tiles:

-
in coordinates $(2j, 3i+2)$, two possible tiles, encoding $x_j$ or $\overline{x_j}$:

-
in coordinates $(2j+1, 3i)$, encoding $x_j$ or $\overline{x_j}$, but no restriction on the left:

-
in coordinates $(2j+1, 3i+1)$:

• for $k$ from $0$ to $n-1$, four tiles same as $(3i+1, 2j)$, but the restriction on the right depends on the vertical color:

-
in coordinates $(2j+1, 3i+2)$, if the clause $C_i$ is $(x\vee y\vee z)$ ($x$, $y$ and $z$ being litterals), then three possible tiles:

Since the number of tiles is $(8n+9)mn$ and the dimension of the rectangle are $3m$ and $2n$, this input is constructible in polynomial time of the size of $\varphi$.

Now let us prove that the reduction is correct.

Suppose that $\varphi$ is satisfiable, and $\mu:\mathcal{V}\to \{0, 1\}$ a boolean assignment satisfying $\varphi$. Then it is possible to cover a rectangle of size $N\times M$ using tiles of $T$:

• for coordinates $(2j, 3i)$, $(2j, 3i+2)$ and $(2j+1, 3i)$, choose the tile of the litteral of value $1$ for $\mu$;

• for coordinates $(2j, 3i+1)$ and $(2j+1, 3i+1)$, choose the tile that can be put on the right of the previous one, with vertical color of a litteral satisfying the clause $C_i$;

• for coordinates $(2j+1, 3i + 2)$, choose the only tile that can be put.

Conversely, if there is a possible tiling of a rectangle of size $N\times M$, then the first column gives a satisfying assignment of $\varphi$:

• the row $2j$ has the same horizontal color and insures that a variable cannot have two boolean assignments;

• the column $3i+1$ has the same vertical color, and the coordinates $(2i+1, 3i+2)$ has necessarily that same color (which is a satisfying litteral for $C_i$);

• other tiles are for verification purposes.

Here's a possible tiling for the formula $(x_1\vee \overline{x_2}\vee x_4)\wedge (x_2 \vee x_3\vee \overline{x_4})$ (which is satisfiable).

StackExchange Computer Science Q#147776, answer score: 4