Table constraints

A table constraint, or an extensional constraint, over a tuple of variables specifies a set of tuples that are allowed (called positive), or disallowed (called negative), for the variables. A positive constraint takes the form X in R, and a negative constraint takes the form X notin R, where X is a tuple of variables $(X_1,\ldots,X_n)$, and R is a table that is defined as a list of tuples of integers, where each tuple takes the form $(a_1,\ldots,a_n)$. In order to allow multiple constraints to share a table, B-Prolog allows X to be a list of tuples of variables. The details of the implementation of table constraints are described in [18].

The following example solves a toy crossword puzzle. A variable is used for each cell, meaning that each slot corresponds to a tuple of variables. Each word is represented as a tuple of integers, and each slot takes on a tuple from a table, which is determined based on the length of the slot. Recall that the notation 0'c denotes the code of the character c.

      crossword(Vars):-
         Vars=[X1,X2,X3,X4,X5,X6,X7], 
         Words2=[(0'I,0'N),
                 (0'I,0'F),
                 (0'A,0'S),
                 (0'G,0'O),
                 (0'T,0'O)],
         Words3=[(0'F,0'U,0'N),
                 (0'T,0'A,0'D),
                 (0'N,0'A,0'G),
                 (0'S,0'A,0'G)],
         [(X1,X2),(X1,X3),(X5,X7),(X6,X7)] in Words2,
         [(X3,X4,X5),(X2,X4,X6)] in Words3,
         labeling(Vars),
         format("~s~n",[Vars]).