# Constraint Lingo

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?
You can try a puzzle yourself
Documentation
```

## A small example

• A puzzle in English
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.
1. Mustafa, who showed his picture fourth, did not use the marker.
2. The child using the pencil showed his or her work right after the one drawn with a paintbrush.
3. Kathy did not show her painting second.
4. Kealoha showed her painting two places after the one drawn in crayon.
• A translation into Constraint 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
```
• The solution computed by Constraint Lingo
```        child      instrument place
========== ========== ==========
frederico  marker     2
kathy      crayon     1
kealoha    paintbrush 3
mustafa    pencil     4
```

## How it all works

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 is written in Perl. It includes the Constraint-Lingo program as comments in the low-level code. We have many versions of the compiler as we experiment with different strategies (standard, best-class, row-number), different logic engines, and various optimizations.
• We support the following logic engines.
• The post-processor is written in Perl; it is specific to the particular compiler used in the previous steps.

## How fast is it?

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.

## How general is Constraint Lingo?

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.