\begin{slide}{Finite-Domain-Constraints (FD)}

Definition
\begin{itemize}
\item prädikatenlogische Formel über mehrsortiger Signatur,
\item für jede Sorte eine endliche Menge
\end{itemize}
Beispiele
\begin{itemize}
\item magisches Quadrat, Sudoku
\item Rösselsprung, $n$-Damen-Problem
\item Graphenfärbungen
\item SAT
\end{itemize}

\end{slide}

\begin{slide}{FD-Lösungsverfahren}

Prinzip (vgl. DPLL für SAT)
  \begin{itemize}
  \item entscheiden:

    eine Variable auswählen, für diese alle möglichen Belegungen ausprobieren
  \item propagieren:

    Menge der möglichen Belegungen anderer Variablen verkleinern
  \end{itemize}

welche Variable wird Entscheidungsvariable?
\begin{itemize}
\item Aktivität
\item Wertebereich 
\end{itemize}

\end{slide}
