Constraint Lingo is a high-level logic-programming language for expressing tabular constraint problems such as those found in logic puzzles. Raphael Finkel developed it starting around 2000 as part of work in Logic Programming with Mirek Truszczynski and Victor Marek.
Example Puzzle Translation into Constraint Lingo Solution How it all works How fast is it? How general is Constraint Lingo? It's available for download You can try a puzzle yourself Documentation
Four children, Kathy, Frederico, Kealoha, and Mustafa, drew pictures for their kindergarten class, each using a different drawing instrument. They then proudly showed their pictures to the class in some order. Determine which instrument each child used and in what order they presented their work given the following four clues.
- Mustafa, who showed his picture fourth, did not use the marker.
- The child using the pencil showed his or her work right after the one drawn with a paintbrush.
- Kathy did not show her painting second.
- Kealoha showed her painting two places after the one drawn in crayon.
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
child instrument place
========== ========== ==========
frederico marker 2
kathy crayon 1
kealoha paintbrush 3
mustafa pencil 4
A compiler translates the Constraint-Lingo program into low-level code, which is then executed by a logic engine. A post-processor formats the result into a table.
The compiler and post-processors are so fast that we never worry about their contribution to the total time. Almost all the 90 or so puzzles we have programmed are solved in less than a second by all versions of the compiler and their associated logic engines. A few take more than 10 seconds with some compilers.
We are able to encode several graph problems in Constraint Lingo, notably 3-coloring, Hamiltonian paths/circuits, and independent sets. A preprocessor converts graphs into equivalent Constraint-Lingo programs.
We continue to develop Constraint Lingo. We are currently adding mappings between solution rows, multiple-selection classes, and limited function symbols.
You can download a copy of our current work from ftp://ftp.cs.uky.edu/cs/software/cl.tar.gz. This code is not production quality; it is work in progress. We would appreciate knowing you have downloaded it and what your experiences are; please mail to raphael_@cs.uky.edu (without the underscore).
We have written several papers on Constraint Lingo. The most current one in Software -- Practice and Experience, Volume 34, number 15, pages 1481-1504, December 2004.
Translations of this page: