sift
Ein SAT-Solver (DPLL) mit einem Toolkit für Aussagenlogik und einem DIMACS-Parser, in Haskell. Er löst echte Instanzen und übersetzt Formeln in CNF (Tseitin).
Ein SAT-Solver auf Basis des DPLL-Algorithmus, geschrieben in Haskell, plus ein Werkzeugkasten für Aussagenlogik: ein DIMACS-Parser und die Übersetzung von Formeln in CNF mit der Tseitin-Methode. Er löst echte Instanzen.
Überblick
sift ist ein SAT-Solver auf Basis des DPLL-Algorithmus, geschrieben in Haskell, zusammen mit einem Werkzeugkasten für Aussagenlogik: einem Parser für das DIMACS-Format und der Übersetzung von Formeln in die CNF-Form mit der Tseitin-Methode. Es ist keine Übung auf dem Papier - es löst echte Instanzen.
SAT ist eines dieser Probleme, die scheinbare Einfachheit mit enormer Tiefe verbinden. Die Frage klingt harmlos, doch ihre Antwort kann Probleme aus völlig anderen Bereichen entscheiden. Dieses Projekt berührt genau diesen Kern, und zwar von einer Seite, die Sie zwingt zu verstehen, warum ein Solver überhaupt funktioniert.
SAT fragt nach etwas scheinbar Banalem: Lassen sich Wahrheitswerte so wählen, dass die ganze Formel wahr wird? Banal bis zu dem Moment, in dem es Hunderte von Variablen gibt und von der Antwort Planung, Schaltungsverifikation oder das Lösen eines Rätsels abhängt. Ein SAT-Solver steckt unter vielen schweren Problemen, die zuerst in seine Sprache übersetzt werden.
Die Standardeingabe ist das DIMACS-Format - jede Zeile ist eine Klausel, Zahlen sind Variablen, ein Minus ist eine Negation, eine Null beendet eine Klausel. Schlichter Text, der überraschend schwere Fragen kodieren kann.
Wie DPLL funktioniert
DPLL ist eine intelligente Suche mit Backtracking. Statt alle Kombinationen zu probieren, wählt es bei jedem Schritt eine Variable, nimmt ihren Wert an und achtet auf zwei Abkürzungen: Hat eine Klausel nur ein noch unentschiedenes Literal, ist dessen Wert erzwungen; kommt eine Variable immer in derselben Form vor, lässt sie sich sofort setzen.
Genau diese zwei Abkürzungen machen den Unterschied zwischen einer Sekunde und einer Ewigkeit. Ohne sie irrt der Solver durch den Baum aller Möglichkeiten; mit ihnen fallen ganze Teilbäume weg, bevor sie überhaupt besucht werden. Sie korrekt zu implementieren ist das Herz des ganzen Solvers.
Tseitin: warum CNF nicht explodiert
DPLL verlangt eine Formel in CNF, aber nicht jede Formel ist es schon. Eine naive Umwandlung kann ihre Größe exponentiell sprengen und ein kleines Problem noch vor dem Start des Solvers in ein riesiges verwandeln. Die Tseitin-Methode führt Hilfsvariablen ein und hält das Wachstum linear.
Formelgröße nach der Umwandlung (orientierend)
Die Tseitin-Methode ist einer dieser Kniffe, die wie Magie aussehen, bis man versteht, warum sie funktionieren. Sie fügt Hilfsvariablen hinzu, die die Formel scheinbar verkomplizieren, in Wahrheit aber ihre Größe retten - ohne sie kann eine naive Umwandlung exponentiell wachsen.
Das Ergebnis: ein Solver, der wirklich löst
Heraus kommt ein funktionierender Solver, der echte Instanzen im DIMACS-Format nimmt und eine Antwort zurückgibt, und unterwegs jede Formel in CNF übersetzt, ohne ihre Größe zu sprengen. Geschrieben in Haskell, weil Mustervergleich und Typen, die die Korrektheit hüten, die Logik fast wie Mathematik lesen lassen. Ein kleines Projekt, das einen sehr tiefen Teil der Informatik berührt - und ihn wirklich löst.
Weitere Projekte
Weitere Projekte aus derselben Kategorie - sehen Sie, wie wir ähnliche Herausforderungen angehen.
Haben Sie ein ähnliches Projekt?
Melden Sie sich - ein Angebot ist kostenlos und kommt innerhalb einer Stunde.