2.8 Constraint Satisfaction Problems (CSP) (BT104CO)

1. What is a CSP?

In the framework of Russell and Norvig, a Constraint Satisfaction Problem (CSP) solves problems by looking at the internal structure of a state (Factored representation), rather than treating it as an Atomic "black box."

X

Variables

The set of items that need to be assigned values (e.g., $\{X_1, X_2...\}$).

D

Domains

The set of all possible values for each variable (e.g., $\{Red, Blue...\}$).

C

Constraints

Mathematical rules specifying which value combinations are allowed.

Core Difference: While standard search looks for a path, a CSP looks for a legal configuration of variables.

2. Types of Constraints

Unary Constraints: Restrict a single variable (e.g., $SA \neq \text{green}$).
Binary Constraints: Relate two variables (e.g., $SA \neq NSW$, common in Map Coloring).
Global Constraints: Involve three or more variables (e.g., $Alldifferent$ in Sudoku).

3. Cryptarithmetic Problems: The Rookie Guide

Solving Cryptarithmetic problems is like being a detective uncovering hidden digits. We use CSP principles: deduction, exhaustion, and "carry" variables.

The Rookie's "Golden Rules"
1. The Leftover 1: Carry over to a new column is always 1.
2. Unique Digits: Each letter is $0-9$. No twins allowed.
3. No Zero Starts: Leading letters (S, M, etc.) cannot be $0$.

Case Study Walkthrough: SEND + MORE = MONEY

Step 1: Find the "Freebie": The sum of two 4-digits makes a 5-digit number. The leading M must be the carry. M = 1.
Step 2: Solve the neighbor: $S + M = MO$. Since $M=1$, then $S+1 = 10+O$. If $S=9$, then O = 0.
Step 3: Solve the bridge: In $N + R = E$, we find that R = 8 (given carries from right).
Step 4: Final Deduction: After testing pairs for $D + E = Y + 10$, we find D=7, E=5, N=6, Y=2.
Result: 9567 + 1085 = 10652

4. 5 Classic Solved Problems

Two + Two = Four
TWO
+ TWO
-----
FOUR

Logic: $R$ is even ($2O$). $F=1$ (carry). If $T=7, O=4 \to R=8$. If $W=3 \to U=6$.

734 + 734 = 1468
Base + Ball = Games
BASE
+ BALL
------
GAMES

Logic: $G=1$ (carry). $A=0$ (since $2A=A$). If $B=7$ (with carry) $\to G=1, A=0$.

7043 + 7055 = 14098
Forty + Ten + Ten = Sixty
FORTY
TEN
+ TEN
-------
SIXTY

Logic: $2N=10 \to N=5$ or $0$. Testing confirms $N=0, E=5, T=8$.

29786 + 850 + 850 = 31486
Eat + That = Apple
EAT
+ THAT
-------
APPLE

Logic: $A=1$ (carry). $T=9$ (needed for carry). $P=0$ ($9+1=10$). $E=8$ ($9+9=18$).

819 + 9219 = 10038

4. Solving CSPs: Backtracking Search

The standard algorithm is Backtracking Search—a Depth-First Search that chooses values for one variable at a time, "backtracking" immediately if a constraint is violated.

MRV Heuristic

Minimum Remaining Values: Pick the variable with the fewest "legal" values left. Also called the Most Constrained Variable.

Degree Heuristic

Choice based on the largest number of constraints on other unassigned variables. Acts as a tie-breaker for MRV.

LCV Heuristic

Least Constraining Value: Choose the value that rules out the fewest choices for its neighbors.

6. Quick Practice & Troubleshooting

1. CP + IS = ART
Hint: $A=1$. Look at $C+I=A$.
2. AA + BB = CCB
Hint: $C=1, A=9$.
3. GO + TO = OUT
Hint: $O=1, T=2$.

Rookie Troubleshooting Guide

  • Stuck? Find the letter that appears most often—that's your "anchor."
  • Contradiction? If you find $E=5$ but $A$ is already $5$, your first guess (usually $S$ or $O$) was wrong. Backtrack!
  • Carry Mark: Always write a small "$1$" above your math columns. It changes everything!

Unit 2 Assignment: CSP Master

Using the **Backtracking Search** logic and **MRV Heuristic**, solve the following 3 problems. Submit your step-by-step deductions.

Task 1: Formalize the "Map Coloring Problem" for 4 neighboring provinces using X, D, and C.
Task 2: Solve the cryptarithmetic puzzle USA + USSR = PEACE.
Task 3: Explain why the Degree Heuristic is used as a tie-breaker for MRV.

Exam Tip

In Cryptarithmetic, never forget the Carry Variables ($c_k$). Without carries, you cannot express the mathematical logic of the column-wise addition correctly in a CSP format.
← Previous: 2.7 Problem-Solving Agents
Next: 2.9 Game Playing →
Back to Course Syllabus

Practice Quiz