Basic Constraint Satisfaction Problem (CSP) with Three Variables and Backtracking

A constraint satisfaction problem (CSP) is defined by: (i) a set of variables, (ii) a domain, and (iii) a set of constraints that restrict combinations of values. In a CSP, the goal is to find an assignment of values to all variables such that all constraints are satisfied.

To make this concrete, we will define a simple CSP with three variables $X, Y, Z$, each having a small finite domain, plus binary constraints that relate pairs of variables. We will then solve it using backtracking search, where we assign variables one by one, check constraint satisfaction so far, and backtrack when we hit a dead end.

CSP components (what you “plug in”)

• Domain: limits the values each variable can take.
• Unary constraint: restricts one variable’s values.
• Binary constraint: restricts allowed value pairs.
• Consistency check: used during backtracking.

A Concrete 3-Variable CSP Example

We define a CSP with three variables:

• $X \in \{1,2,3\}$
• $Y \in \{1,2,3\}$
• $Z \in \{1,2,3\}$

And constraints:

1. $X \neq Y$ (all different between $X$ and $Y$)
2. $Y \neq Z$ (all different between $Y$ and $Z$)
3. $X = Z$ (ties $X$ and $Z$ together)

This CSP is small but illustrates everything you asked for: the role of the domain (what values are even allowed), and the role of the constraints (which combinations/relations are permitted).

Formal CSP definition

• Variables: $V=\{X,Y,Z\}$
• Domains:
  $D(X)=D(Y)=D(Z)=\{1,2,3\}$
• Constraints:
  • $C_{XY}: X \neq Y$
  • $C_{YZ}: Y \neq Z$
  • $C_{XZ}: X = Z$

What constraints do (intuitively)

• The domain says “you may try these values.”
• The constraints say “you may not keep these combinations if they violate the rules.”

So in backtracking, we don’t just search blindly—we prune when the partial assignment already violates any constraint.

Role of the Domain and Constraints (in backtracking)

1) Domain controls branching factor

Backtracking assigns values from each variable’s domain. If $D(X)$ has size $k$, then at the point when you pick $X$, there are up to $k$ choices. Smaller domains generally make search faster.

2) Constraints control pruning

A constraint can rule out:

• complete assignments (when all involved variables are assigned), and
• partial assignments (when some involved variables are assigned).

For our example:

• If you already assigned $X$ and you try $Y$, the constraint $X \neq Y$ can reject a candidate immediately.
• If you assigned $Y$ and you try $Z$, the constraint $Y \neq Z$ can reject immediately.
• If you attempt to maintain $X = Z$, then once $X$ is assigned, $Z$ becomes forced to that value (or rejected if you try something else).

Backtracking Search Tree (visual)

Below is a simplified search tree showing how constraints prune choices.