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}