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)