34/110
\begin{frame}{Bounded Tiling Problem}
\begin{block}{}
Given a finite collection of \emph{types} of $1 \times 1$ \emph{tiles} with a \emph{colour} on each side.
(There are infinitely many tiles of each type.)
\end{block}

\begin{exampleblock}{}
\begin{center}
\begin{tikzpicture}[default,scale=.9]
\tile{0}{0}{g}{b}{r}{b}
\tile{2}{0}{r}{b}{g}{b}
\tile{4}{0}{r}{z}{g}{b}
\end{tikzpicture}
\end{center}
\end{exampleblock}
\pause

\begin{goal}{}
\emph{Bonded tiling problem}: the input is
$n \in \mathbb{N}$,
a finite collection of types of tiles,
the first row of $n$ tiles.
\smallskip

\alert{Is it possible to tile an $n \times n$ field (with the given first row)?}
\smallskip

When connecting tiles, the touching side must have the same colour.
Tiles must not be rotated.
\end{goal}
\pause

\begin{exampleblock}{}
Example $n = 2$:\vspace{-3.5ex}
\begin{center}
\begin{tikzpicture}[default,scale=.9]
\tile{0}{0}{g}{b}{r}{b}
\tile{1}{0}{r}{b}{g}{b}
\node [scale=.7,anchor=north,rectangle] at (1,-.1) {first row};
\node [scale=.7,anchor=north,rectangle] at (4,-.1) {incomplete tiling};
\node [scale=.7,anchor=north,rectangle] at (7,-.1) {correct tiling};

\tile{3}{0}{g}{b}{r}{b}
\tile{4}{0}{r}{b}{g}{b}
\tile{3}{1}{r}{z}{g}{b}

\tile{6}{0}{g}{b}{r}{b}
\tile{7}{0}{r}{b}{g}{b}
\tile{6}{1}{r}{b}{g}{b}
\tile{7}{1}{g}{b}{r}{b}
\end{tikzpicture}\vspace{-.5ex}
\end{center}
\end{exampleblock}
\end{frame}