Constraint Lingo

Originalquelle: http://www.cs.uky.edu/~raphael/cl

Constraint Lingo ist eine übergeordnete Logikprogrammiersprache zum Ausdrücken tabellarischer Constraint-Probleme, wie sie beispielsweise in Logikrätseln vorkommen. Raphael Finkel entwickelte es ab 2000 im Rahmen der Arbeit mit Mirek Truszczynski und Victor Marek in Logic Programming .

Beispiel- 
  Puzzle- 
  Übersetzung in Constraint Lingo- 
  Lösung 
Wie alles funktioniert 
Wie schnell ist es? 
Wie allgemein ist Constraint Lingo? 
Es ist zum Download verfügbar. 
Sie können ein Puzzle selbst ausprobieren. 
Dokumentation

Ein kleines Beispiel

  • Ein Puzzle auf EnglischVier Kinder, Kathy, Frederico, Kealoha und Mustafa, zeichneten Bilder für ihre Kindergartenklasse, wobei jedes ein anderes Zeicheninstrument verwendete. Dann zeigten sie der Klasse stolz ihre Bilder in einer bestimmten Reihenfolge. Bestimmen Sie anhand der folgenden vier Hinweise, welches Instrument jedes Kind verwendet hat und in welcher Reihenfolge es seine Arbeit präsentierte.
    1. Mustafa, der sein viertes Bild zeigte, benutzte den Marker nicht.
    2. Das Kind, das den Bleistift benutzte, zeigte seine Arbeit direkt nach der mit einem Pinsel gezeichneten.
    3. Kathy zeigte ihr Bild nicht als zweites.
    4. Kealoha zeigte ihr Gemälde zwei Stellen nach dem in Buntstift gezeichneten.
  • Eine Übersetzung in Constraint LingoCLASS Kind: kathy Frede Kealoha mustafa CLASS Ort: 1 .. 4 CLASS Instrument: Kreide Bleistift Marker Pinsel # Hinweis 1 KONFLIKT mustafa Marker ERFORDERLICH mustafa 4 # Hinweis 2 OFFSET 1 Ort: Pinsel Bleistift # 3 Hinweis KONFLIKT kathy 2 # Hinweis 4 OFFSET 2 Ort: Wachsmalstift Kealoha
  • Die von Constraint Lingo berechnete Lösung Kind Instrument Platz ================================ frederico marker 2 kathy crayon 1 kealoha pinsel 3 mustafa pencil 4

Wie funktioniert das alles?

Ein Compiler übersetzt das Constraint-Lingo-Programm in Low-Level-Code, der dann von einer Logik-Engine ausgeführt wird. Ein Postprozessor formatiert das Ergebnis in einer Tabelle.

  • Der Compiler ist in Perl geschrieben. Es enthält das Constraint-Lingo-Programm als Kommentare im Low-Level-Code. Wir haben viele Versionen des Compilers, während wir mit verschiedenen Strategien (Standard, Best-Class, Zeilennummer), verschiedenen Logik-Engines und verschiedenen Optimierungen experimentieren.
  • Wir unterstützen die folgenden Logik-Engines .
  • Der Postprozessor ist in Perl geschrieben. es ist spezifisch für den bestimmten Compiler, der in den vorherigen Schritten verwendet wurde.

Wie schnell ist es

Der Compiler und die Postprozessoren sind so schnell, dass wir uns keine Sorgen um ihren Beitrag zur Gesamtzeit machen. Fast alle von uns programmierten 90 Rätsel werden von allen Versionen des Compilers und den zugehörigen Logik-Engines in weniger als einer Sekunde gelöst. Einige benötigen bei einigen Compilern mehr als 10 Sekunden.

Wie allgemein ist Constraint Lingo?

Wir können in Constraint Lingo mehrere Grafikprobleme kodieren, insbesondere 3-farbig, Hamiltonpfade / -schaltungen und unabhängige Mengen. Ein Präprozessor konvertiert Diagramme in entsprechende Constraint-Lingo-Programme.

Wir entwickeln Constraint Lingo weiter. Derzeit fügen wir Zuordnungen zwischen Lösungszeilen, Mehrfachauswahlklassen und eingeschränkten Funktionssymbolen hinzu.

Es ist zum Download verfügbar

Sie können eine Kopie unserer aktuellen Arbeit von ftp://ftp.cs.uky.edu/cs/software/cl.tar.gz herunterladen . Dieser Code ist keine Produktionsqualität. es ist work in progress. Wir würden uns freuen zu wissen, dass Sie es heruntergeladen haben und welche Erfahrungen Sie gemacht haben. Bitte mailen Sie an raphael_@cs.uky.edu (ohne Unterstrich).

Sie können ein Puzzle selbst ausprobieren

Upload aus dieser Datei:  
oder geben Sie Ihr Constraint Lingo-Programm hier ein: 

Dokumentation

Wir haben mehrere Artikel über Constraint Lingo geschrieben. Das aktuellste in Software – Praxis und Erfahrung, Band 34, Nummer 15, Seiten 1481-1504, Dezember 2004.