Constraint Processing

chapter 2

Constraint Networks

Nature, like liberty, is but restrain’d by the same laws which first herself ordain’d.

Alexander Pope, An Essay on Criticism

In this chapter we begin formally modeling constraint satisfaction problems as constraint networks. The initial formal work on constraint networks introduced by Montanari (1974) was restricted to binary constraints, defined on pairs of variables only. Much of the early research, experiments in particular, was limited to the binary case. Indeed, it is possible to show that any set of constraints can be mapped to the binary case. Nevertheless, we will always assume the general case, where constraints are defined on sets of variables of arbitrary size, and will explicitly refer to the special ...