Die Anwendung von Konsistenztechniken führt i.A. nicht zu einer Lösung eines CSP. Es ist daher notwendig, zusätzliche Algorithmen zum Auffinden von Lösungen anzuwenden. Diese Suchverfahren können nach dem Herstellen einer lokalen Konsistenz, oder kombiniert mit Konsistenztechniken zum Einsatz kommen (vgl. Güsgen, 2000, S. 275).
Suchverfahren zur Bestimmung von Lösungen in einem CSP werden unterschieden in systematische und stochastische Verfahren. In diesem Abschnitt werden ausschließlich systematische Suchverfahren vorgestellt. Systematische Verfahren werden auch globale Suchverfahren genannt, da sie auf das CSP in seiner gesamten Struktur angewendet werden. Im Gegensatz zu stochastischen Verfahren sind sie vollständig, d.h. es ist garantiert, dass alle existierenden Lösungen gefunden werden, wenn es welche gibt. Stochastische Suchverfahren sind unvollständig und betrachten das CSP anhand lokaler Kriterien. Sie garantieren nicht, dass eine gefundene Lösung globale Gültigkeit besitzt und werden deshalb auch lokale Suchverfahren genannt (vgl. Abschnitt 5.2.2).
Bei der Anwendung von Suchverfahren nehmen die Constraints i.A. eine passive Rolle ein, da die Strategie zur Lösung des Problems durch den Lösungsalgorithmus vorgegeben ist. Die Constraints werden durch das Suchverfahren dazu genutzt, durch Testen von generierten (Teil-)Lösungen Inkonsistenzen, d.h. ungültige Variablenbelegungen, zu entdecken und ungültige Werte auszuschließen. Bei dieser a posteriori Reduktion des Suchraums können die Eigenschaften eines CSP genutzt werden, um effizient zu einer Lösung zu gelangen.
Die Performanz der Suche kann gesteigert werden, indem der Suchraum reduziert wird. Dies kann durch die Kontrollstrategie des Suchalgorithmus beeinflusst werden, durch Herstellen eines lokalen Konsistenzgrades, durch die Reihenfolge, in der die Variablen ausgewählt werden und, wenn nur eine einzige Lösung benötigt wird, durch die Reihenfolge der Werte in den Domänen, mit denen die Variablen während des Suchvorgangs belegt werden (vgl. Dechter und Frost, 2002, S. 155 f.). Infolgedessen wurden zwei Arten von Vorgehensweisen entwickelt: Zum einen kann ein Preprozessing des CSP vor der eigentlichen Suche stattfinden. Hier kommen häufig Algorithmen zur Herstellung von Kanten- und Pfadkonsistenz sowie Heuristiken zur Generierung einer statischen Variablenordnung zum Einsatz. Zum anderen gibt es Verfahren, die während der Suche mittels look-ahead- und look-back-Strategien die Effizienz der Suche beeinflussen. Dies sind z.T. kombinierte Verfahren, die zur Problemreduktion dynamisch während des Suchvorgangs Konsistenztechniken und Heuristiken einsetzen. Die Strategien der hier beschriebenen Suchverfahren können, wie in Tabelle 5.2 dargestellt, in drei Kategorien klassifiziert werden vgl. Dechter und Frost, 1998, S. 3 f.; Dechter und Frost, 2002, S. 155 f.; Tsang, 1993, S. 119 f.:
Im Folgenden werden eine Reihe von systematischen Suchverfahren vorgestellt, die zur Bestimmung von Lösungen in FCSPs geeignet sind. Die Auflistung erhebt keinen Anspruch auf Vollständigkeit, sondern gibt einen Überblick über die grundlegenden bzw. gängigen Techniken.