Minesweeper-Konsistenz
In Kapitel 13 wird gezeigt, dass MINESWEEPER-CONSISTENCY NP-vollständig ist. Dazu wurde eine Reduktion von SAT konstruiert. Illustriert wurde die Konstrukion mit Minesweeper-Konsistenz-Problemen die die logischen Gatter realisieren. Die Java-Anwendung in minesweeper-1.0.tar.gz wurde verwendet, um diese Illustrationen zu erstellen.
Ausgehend von Bomben, die der Benutzer platziert, versucht das Programm, weiter Bomben zu platzieren, solange diese durch die Regeln eindeutig bestimmt sind. Das Programm ist nicht besonders intelligent, es unternimmt kein Backtracking um die vollständige Konsistenz festzustellen.