Constraint Lingo syntax.

This document describes the syntax and sematics for representing constraint
problems with tabular solution.

Any input line that starts with # is ignored.  The solution of a constraint
problem is a table with rows and columns.  The table is filled with elements.

1. Columns are declared by CLASS, PARTITION, POWERCLASS, and MAP.
Each introduces the name of a column and constrains the values in that column.

Classes
	Example:
		CLASS defense: dutch french gruenfeld morphy sicilian
	General form:
		CLASS classname: [member1 ... | member1 .. member2 [circular]]
	Restrictions: the classname must be new.
		Except for numeric classes, all classes must have the same number
		of elements.  Numeric classes may exceed that number.
	Semantics: The class's column in the solution table contains distinct
		members of the class as elements.  Unless .. notation is
		used, every member of the class appears somewhere in the
		column.  If the form member1 .. member2 is used, both members
		must be numeric; all values in the range are included, but
		not all must participate in the class's column in a
		solution.  If the "circular" note is appended, then member1
		must be 1.  In this case, the values of the class are taken
		as circular for purposes of ordering; member2 + 1 is member1.

Partitions
	Example:
		PARTITION gender: male female
	General form:
		PARTITION partitionname: member1 member2 ...
	Restrictions: the partitionname must be new.
	Semantics:
		The partition's column in the solution table contains members of the
		partition as elements.  It is not required that all members are used.
		It is not required that rows have distinct entries in this column.
		See NONEMPTY, USED.
	Comment: Use a variable instead of a two-valued partition if you know that
		only one row has one of the values, such as "winner".

Power Classes (not accepted by Eclipse)
	Example:
		POWERCLASS miseries(2,3): cold cloudy rainy dark smelly
	General form:
		POWERCLASS powerclassname(m,n): member_list
	Restrictions:
		The powerclassname must be unique.  m must be less than or equal to n.
	Semantics:
		The power class's column in the solution table contains sets of the
		given members.  Each entry is distinct and contains
		between m and n (inclusive) members.
		All constraints
		that refer a powerclass member refers to all rows associated with
		that member.

Maps (not accepted by Eclipse)
	Example:
		MAP hero NON-REFLEXIVE
	General form:
		MAP mapname [SYMMETRIC ASYMMETRIC ONTO NON-REFLEXIVE]
	Restrictions:
		The mapname must be unique.
	Semantics:
		The map's column does not have any declared members.  Instead,
		each entry in the map's column refers to an entire row in the solution
		table. If "ONTO" is specified, then each row in the solution table is
		mapped to only one row, and each row refers to only one row in the
		solution table. If "NON-REFLEXIVE" is specified, then no row in the
		solution table refers to itself. If "SYMMETRIC" is specified, then
		whenever row A refers to row B, row B refers to row A. If
		"NON-SYMMETRIC" is specified, then no row in the solution table refers
		to its referer. 

2. A "row reference" is any class, partition, or powerclass member. Row
references used in constraints refer to all rows that have the given member in
its appropriate column; in the case of partitions and powerclasses, there may
be zero, one, or more such rows.  If the same member is declared in several
columns, a row reference based on it must be prefixed with the column name and
a dot, as in person.green and color.green.  In addition, a row reference may be
introduced by VAR.

Row reference
	Example:
		VAR jacksbrother
	General form:
		VAR varname
	Restrictions: The varname must be new and unique.
	Semantics: The varname refers to a row of the solution.
	Comment: Use a variable instead of a two-valued partition if you know that
		only one row has one of the values, such as "winner".

3.  Inter-row constraints are introduced by REQUIRED, AGREE, IMPLIES,
SAME, DIFFER, CONFLICT, and MATCH.

Complete intersection
	Example:
		REQUIRED dutch bishop 
	General form:
		REQUIRED rowref1 rowref2 ...
	Semantics:
		All row references refer to the same set of rows.

Boolean complete intersection
	Example:
		REQUIRED dutch bishop XOR dutch rook
	General form:
		REQUIRED rowref1 rowref2 [OR | XOR | IFF] rowref3 rowref4
	Semantics:
		Let A mean that rowref1 and rowref2 refer to the same rows in the
		solution; similarly, let B mean that rowref3 and rowref4 refer to the
		same rows of the solution.  Depending on the form, A OR B must hold, or
		A XOR B, or A IFF B.

Subsets based on partition
	Example:
		AGREE male: jones smith
	General form:
		AGREE partitionmember: rowref1 ...
	Semantics:
		All the rows specified by the row references must contain the given
		partition member in its column, although other rows may also contain
		it.
	Warning:
		Such a requirement should often be coupled with
			CONFLICT member1 ...
	Note:
		For backward compatibility, REQUIRED may be used instead of
		AGREE; this use is deprecated.

Coincidence of partition
	Example:
		SAME gender: soap rook
	General form:
		SAME partitionname: rowref1 rowref2 ...
	Semantics:
		The rows defined by the rowrefs must have the same value in the
		partition's column.  The rowrefs might actually refer to the same rows.
	Warning:
		Such a requirement should often be coupled with
			CONFLICT rowref1 rowref2

Conflict of partition
	Example:
		DIFFER gender: soap rook
	General form:
		DIFFER partitionname: rowref1 rowref2 ...
	Semantics:
		The rows defined by the rowrefs must have different values in the
		partition's column.  In particular, none of the rowrefs can refer to
		more than one row.

Subsets based on powerclass
	Example
		IMPLIES cold rainy
	General form:
		IMPLIES rowref powerclassmember
	Semantics:
		All rows specified by the rowref must all be associated with the
		powerclassmember, but there may be other rows associated with the
		powerclassmember.	

Empty intersection
	Example:
		CONFLICT dutch clyde
	General form:
		CONFLICT rowref1 rowref2 ...
	Semantics:
		The rows specified by each of the row specifiers must not overlap.

Permutation
	Example:
		MATCH aunt sister mother , french silver nighttable
	General form:
		MATCH rowref1 ... , rowref2 ...
	Semantics:
		Every row of the solution determined by a rowref before the comma
		must be the same as exactly one row determined by a rowref after the
		comma, and vice-versa.  Furthermore, all the rowrefs before the comma
		refer to different rows, as do all the rowrefs after the comma.

4.  Multiple-column constraints are introduced by UNIQUE and DIFFER

Uniqueness of multiple partitions
	Example:
		UNIQUE floor wing
	General form:
		UNIQUE partition1 partition2
	Semantics:
		No two rows may agree on their values for the two columns named by
		partition1 and partition2.

Non-overlap of multiple maps
	Example:
		DIFFER receiver sender
	General form:
		DIFFER map1 map2 ...
	Semantics:
		For all rows of the solution, the given map columns contain
		different pointers.

5.  Cardinality constraints are introduced by USED.

How many rows a rowref refers to
	Example:
		USED male <= 2
	General form:
		USED n <= rowref <= m
	Semantics:
		The number of rows refered to by the row reference must be between n
		and m, inclusive.  If "n <=" is absent, it defaults to "1 <=".  If "<=
		m" is absent, no upper bound is applied.  This construct is useful to
		specify that a particular member of an underspecified numeric class is
		used. It is never necessary to say explicitly that a VAR is used.

6.  Numeric constraints are introduced by BEFORE, OFFSET, and AGGREGATE.

Simple order constraint
	Example:
		BEFORE order: soap radio
	General form:
		BEFORE class: rowref1 rowref2
	Restrictions:
		The members of the class must all be numeric.
		The two row references must not both be members of the given class.
	Semantics:
		All rows specified by rowref1 must have a smaller value in the given
		class's column than all rows specified by rowref2. 

Order constraint
	Example:
		OFFSET 1 day: soap radio
	General form:
		OFFSET [ + | * | +- | > | ! | !+- ] n class: rowref1 rowref2
	Restrictions:
		The members of the class must all be numeric.
	Semantics:
		The row defined by rowref1 has value v1 in the given class's column.
		The row defined by rowref2 has value v2 in the given class's column.
		(Both row references must specify a single row.)
		v1 op n = v2, where op is +, *, or +- (read: plus or minus).
		The > operator means "plus n < v2" (read: offset more than n).
		The ! operator means "plus n != v2" (read: offset is not n).
	Comment:
		BEFORE class: member1 member2
			is identical to
		OFFSET >0 class: member1 member2
	Comment:
		It would be nice to have >=.

Numeric class totals (not accepted by mchaff)
	Example:
		CLASS value: 1 .. 10
		AGGREGATE + value 15
	General form:
		AGGREGATE [*|+] name amount
	Restrictions:
		The name must be a PARTITION or a CLASS.
	Semantics:
		Not all the values of the given PARTITION or CLASS need to be used, in
		general, but those that are used either sum to (+) or multiply to (*)
		the given value.
	Comment:
		The various logic back-ends are quite different in their ability to
		handle AGGREGATE.  Dlv is the fastest (but it currently has a bug for
		multiplication).  Asp is slow for addition, and extremely slow for
		multiplication.  Eclipse is slow for all AGGREGATEs.

7.  Function-symbol constraints

A function symbol is an expression of the form columnname(rowref), where the
columnname may be the name introduced by CLASS, PARTITION, POWERCLASS, or MAP.
In the first three cases, the function symbol refers to a particular row and
column of the solution.  In the case of MAP, it refers to a row.  Function
symbols participate in the SET syntax.

Equality and inequality constraint
	Example:
		SET costume(sam) = tiger
	General form:
		SET columnname(rowref) [ = | != ] member
		SET member [ = | != ] columnname(rowref)
		SET mapname(rowref1) [ = | != ] mapname(rowref2)
	Restrictions: 
		The members must be defined as CLASS, PARTITION, or POWERCLASS
		members.  If the columnname is not a MAP, then the member must belong
		to the given column.
	Semantics:
		If the function is a MAP, then the row of the solution identified by
		the left-hand side refers to (=) or does not refer to (!=) the row
		identified by the right-hand side.  If the function is a CLASS,
		PARTITION, or POWERCLASS, then the constraint follows the semantics of
		the REQUIRED (=) or CONFLICT (!=) as defined earlier.

Arithmetic constraint
	Example:
		SET position(sam) + 2 = position(tiger)
		SET position(sam) * 2 = position(tiger)
	General form:
		SET columnname(rowref1) [+|*] value [=|!=|>=|>] classname(rowref2)
	Restrictions:
		The classname must be a predefined CLASS, PARTITION, or POWERCLASS. 
	Semantics:
		The two cells of the solution are arithmetically related by the
		given expression.

8. Direct logic-engine code

Code written directly for the underlying logic engine, such as smodels or asps,
can be included in the program.  This feature is meant to be used by experts
and designers.

	Example:
		PASS sm2tn :- food_day(mushrooms, 3) .
	General form:
		PASS method arbitrary-logic-code
	Restrictions:
		The method must be one of: sm2, sm2tn, dlv, dlv2tn, ndcs, ndcs2tn, ecl.
	Semantics:
		The arbitrary code is passed directly on to the back-end logic engine.
		Its meaning depends on the rest of the code generated by the translator.
		A translator for one method will not pass code intended for a different
		method.
	Comment:
		You need to know how constraints are translated to make any use of
		this feature.

9.  Missing features.

Although Constraint Lingo can handle a wide variety of constraints, some
constraints have appeared in tabular puzzles that Constraint Lingo cannot yet
handle.

	Life is a cabaret (Oct 99: 13)
		In at least three cases, m1 = m2 + offset
		m1 is offset +-1 from unknown m2; m2 is offset +-2 from m3.
	Geronimo (Oct 99: 25)
		neither m1 nor m2 was m3 or m4 (I can manually build 4 cases)
	Rafflemania (Oct 99: 39)
		at least two members of subclass1 are consecutive in class2
		no members of subclass1 are consecutive in class2
	Sounds of Music (Dec 99: 18)
		IF m1 m2 THEN m3 m4 (not the same as IFF)