Table constraints

A table constraint, or 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 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 detail of the implementation of table constraints is described in [18].

The following example solves a toy crossword puzzle. A variable is used for each cell, so 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]).