Contrainte Lingo

Original: http://www.cs.uky.edu/~raphael/cl.html

 

Contrainte Lingo est un langage de programmation logique haut niveau pour exprimer des problèmes de contrainte tabulaires tels que ceux trouvés dans les puzzles de logique. Raphael Finkel développé à partir d’environ 2000 dans le cadre des travaux en logique de programmation avec Mirek Truszczynski et Victor Marek.

Exemple

Puzzle
Traduction en contrainte Lingo
Solution

Comment tout cela fonctionne
Quelle vitesse est-ce ?
Comment général est contrainte de Lingo ?
Il est disponible en téléchargement
Vous pouvez essayer un puzzle vous-même
Documentation

Un petit exemple

  • Un puzzle en anglais

Quatre enfants, Kathy, Frederico, Kealoha et Mustafa, dessiné pour leur classe de maternelle, chaque utilisation d’un instrument de dessin différent. Puis, ils ont montré fièrement leurs photos à la classe dans un certain ordre. Déterminer quel instrument chaque enfant utilisé et dans quel ordre ils ont présenté leur travail étant donné les indices suivants quatre.

  1. Mustafa, qui a montré sa photo quatrième, n’a pas utilisé le marqueur.
  2. L’enfant en utilisant le crayon a montré son travail juste après celui dessiné avec un pinceau.
  3. Kathy n’a pas montré son deuxième peinture.
  4. Kealoha a montré ses deux lieux de peinture après celui dessiné au crayon.
  • Une traduction en contrainte Lingo

CLASS child: kathy frederico kealoha mustafa
CLASS place: 1 .. 4
CLASS instrument: crayon pencil marker paintbrush

# clue 1
CONFLICT mustafa marker
REQUIRED mustafa 4
# clue 2
OFFSET 1 place: paintbrush pencil
# clue 3
CONFLICT kathy 2
# clue 4
OFFSET 2 place: crayon kealoha

 

  • La solution calculée par contrainte Lingo

child      instrument place
========== ========== ==========
frederico  marker     2
kathy      crayon     1
kealoha    paintbrush 3
mustafa    pencil     4

Comment tout cela fonctionne

Un compilateur traduit le programme contrainte-Lingo en code de bas niveau, qui est ensuite exécutée par un moteur de logique. Un post-processeur met en forme le résultat dans un tableau.

  • Le compilateur est écrit en Perl. Il comprend le programme de contrainte-Lingo en tant que commentaires dans le code de bas niveau. Nous avons de nombreuses versions du compilateur que nous expérimentons avec des stratégies différentes (standard, inégalée,-numéro de ligne), les moteurs de logique différente et diverses optimisations.
  • Nous soutenons les moteurs suivants de la logique.
  • Le post-processeur est écrit en Perl ; Il est spécifique au compilateur particulier utilisé dans les étapes précédentes.

Quelle vitesse est-ce ?

Le compilateur et les post-processeurs sont si rapides que nous nous inquiétons jamais de leur contribution à la durée totale. Presque tous les puzzles 90 ou alors que nous avons programmé sont résolus en moins d’une seconde par toutes les versions du compilateur et de leurs moteurs logique associé. Quelques-uns prennent plus de 10 secondes avec certains compilateurs.

Comment général est contrainte de Lingo ?

Nous sommes capables d’encoder plusieurs problèmes de graphique dans le jargon de la contrainte, notamment 3-Coloriage, hamiltonien chemins/circuits et séries indépendantes. Un préprocesseur convertit les graphiques dans les programmes de contrainte-Lingo équivalents.

Nous continuons à développer le jargon de la contrainte. Nous ajoutons actuellement les mappages entre les lignes de la solution, les classes de sélection multiple et symboles de fonction limitée.

Il est disponible en téléchargement

Vous pouvez télécharger une copie de notre travail actuel de ftp://ftp.cs.uky.edu/cs/software/cl.tar.gz. Ce code n’est pas la qualité de la production ; Il est en cours. Nous apprécierions sachant que vous avez téléchargé et quelles sont vos expériences ; s’il vous plaît mail à [email protected] (sans le trait de soulignement).

Vous pouvez essayer un puzzle vous-même
Télécharger ce fichier :
ou entrez votre contrainte Lingo programme ici :

 

CLASS child: kathy frederico kealoha mustafa
CLASS place: 1 .. 4
CLASS instrument: crayon pencil marker paintbrush# clue 1

CONFLICT mustafa marker
REQUIRED mustafa 4

# clue 2

OFFSET 1 place: paintbrush pencil

# clue 3

CONFLICT kathy 2

# clue 4

OFFSET 2 place: crayon kealoha

 

Envoyer Fichier clair

Documentation

Nous avons écrit plusieurs articles sur le jargon de la contrainte. Celle plus récente de Software–Practice and Experience, Volume 34, numéro 15, p. 1481-1504, décembre 2004.

Comments are closed.