Ebben a fejezetben megmutatjuk azt, hogy ha az állapotokat nem egyszerűen kis fekete dobozoknak tekintjük, akkor új hatékony keresési módszerek egész sorához jutunk, valamint jobban megértjük a probléma struktúráját és komplexitását.

A 3. és a 4. fejezetben azt az elképzelést jártuk körbe, hogy a problémákat állapottérbeli kereséssel lehet megoldani. A tárgyterületre jellemző heurisztikák segítségével értékelhetjük ezeket az állapotokat és ellenőrizhetjük, hogy nem járunk-e célállapotban. A keresési algoritmus szempontjából azonban mindegyik állapot egy megkülönböztetés nélküli belső struktúrájú fekete doboz (black box). Az állapotokat egy tetszőleges adatstruktúra reprezentálja, amelyhez a problémára jellemző rutinokkal lehet hozzáférni: az állapotátmenet- és a heurisztikafüggvénnyel, valamint a célállapotteszttel.

A fejezetben a kényszerkielégítési problémákkal (constraint satisfication problems) foglalkozunk, amikor az állapotok és a célteszt illeszkedik egy szabályos, strukturált és elég egyszerű reprezentációhoz (lásd 5.1. alfejezet). Az állapotstruktúra segítségével keresési algoritmusokat lehet definiálni, és nem problémaspecifikus, hanem általános célú heurisztikák használatával nagy problémák megoldása is lehetővé válik (lásd 5.2. és 5.3. alfejezet). Talán a legfontosabb azonban az, hogy a célteszt szabályos reprezentációja feltárja magának a problémának a struktúráját (lásd 5.4. alfejezet). Ez pedig módszereket ad a kezünkbe a probléma dekompozíciójára, és lehetővé teszi, hogy megértsük a probléma struktúrája és a megoldás nehézsége közötti szoros kapcsolatot.