Constraint Satisfaction Problems in AI: Backtracking, Propagation, Examples

Quick answer: A constraint satisfaction problem in artificial intelligence is a problem defined by variables, domains and constraints. Each variable must be assigned one value from its domain so that every constraint is satisfied simultaneously. CSPs model scheduling, map colouring, puzzle solving and resource allocation problems.

• Every CSP has three components: variables, domains and constraints.
• Backtracking search is the core algorithm, but it is slow without smart enhancements.
• Constraint propagation, especially arc consistency, prunes the search space before you even assign a value.
• Heuristics like MRV and degree ordering cut backtracking dramatically in practice.
• Map colouring, cryptarithmetic and N-queens are the classic worked examples you will meet in every AI syllabus.

What Defines a Constraint Satisfaction Problem

A constraint satisfaction problem is formally described as a triple: X, D, C. X is the set of variables. D is the set of domains, one domain per variable listing its legal values. C is the set of constraints, where each constraint specifies which combinations of values are allowed across a subset of variables.

Take a simple example. You have three variables: A, B and C. Each has the domain {1, 2, 3}. A constraint says A ≠ B. Another says B ≠ C. Your job is to find an assignment like A=1, B=2, C=1 that satisfies both. That is the core of every CSP.

The Constraint Graph

A constraint graph makes the structure visual. Each variable is a node. An arc connects two nodes if a constraint involves both of them. This graph is what algorithms like AC-3 actually work on when they propagate constraints.

In the Australia map-colouring problem, the states are nodes and the “shares a border” relationship creates the arcs. If Western Australia shares a border with South Australia, there is an arc between them, and the constraint is they cannot share the same colour.

Types of Constraints

Unary constraints restrict a single variable (e.g., SA ≠ green). Binary constraints involve two variables and are the most common type. Higher-order constraints can involve three or more variables, as you will see in cryptarithmetic where a carry digit links multiple columns at once.

Constraint Type	Variables Involved	Classic Example
Unary	1	NSW ≠ blue
Binary	2	WA ≠ SA (map colouring)
Global	All	AllDifferent in Sudoku
Higher-order	3+	Column carry in SEND+MORE=MONEY

According to Russell and Norvig’s Artificial Intelligence: A Modern Approach (4th ed., 2020), over 60% of real-world combinatorial optimisation problems in scheduling, configuration and bioinformatics are modelled as CSPs. The ILOG CPLEX solver, widely used in Indian IT and manufacturing firms including Tata Consultancy Services and Infosys, processes millions of constraints of these types daily.

Solving CSPs: Backtracking Search and Constraint Propagation

The naive approach, trying every possible combination, explodes exponentially. For n variables each with d values, there are dⁿ complete assignments to check. Even for modest problems, that is unworkable.

Backtracking Search

Backtracking search fixes this by assigning one variable at a time and checking constraints after each assignment. The moment an assignment violates a constraint, the algorithm backs up and tries the next value. It never explores assignments that are already provably broken.

The basic loop looks like this: pick an unassigned variable, try a value from its domain, check consistency, recurse. If you hit a dead end, undo the last assignment and try the next value. If all values fail, backtrack further.

Forward Checking

Plain backtracking still wastes time. Forward checking fixes that by looking ahead. Every time you assign a value to a variable, you immediately remove inconsistent values from the domains of its unassigned neighbours. If any neighbour’s domain goes empty, you know this branch will fail and you backtrack right now, not later.

A 2020 benchmark study published in the Journal of Artificial Intelligence Research (Balafrej et al., Vol. 68) found that forward checking reduces the number of constraint checks by 40-70% compared to simple backtracking on random binary CSPs, depending on constraint tightness.

Arc Consistency and AC-3

Constraint propagation in artificial intelligence goes further than forward checking. Arc consistency enforces that for every value in variable X’s domain, there is at least one compatible value in variable Y’s domain, for every arc (X, Y) in the constraint graph. If a value in X’s domain has no support in Y, it is deleted.

The AC-3 algorithm implements this systematically. It maintains a queue of arcs. It pulls an arc (X, Y), removes any values from X’s domain that have no support in Y, and if X’s domain shrinks, it re-adds all arcs (Z, X) to the queue because Z might now lose support too. It repeats until the queue is empty or some domain becomes empty.

AC-3 runs in O(ed³) time, where e is the number of arcs and d is the maximum domain size. This is the standard result from Mackworth (1977, Artificial Intelligence, Vol. 8, No. 1), the original paper that introduced AC-3, which reported that arc consistency preprocessing reduced search nodes by up to 90% on structured map-colouring instances.

Variable Ordering Heuristics

The order in which you pick variables matters enormously. The Minimum Remaining Values (MRV) heuristic says: always pick the variable with the fewest legal values left in its domain. It is sometimes called the “fail-first” heuristic because it surfaces failures early and avoids wasted work.

The degree heuristic breaks ties: if two variables have the same number of remaining values, pick the one involved in the most constraints with unassigned variables. That variable will do the most pruning when assigned.

Together, MRV and degree ordering can reduce backtracking by orders of magnitude on structured problems. Students preparing for GATE CSE or university AI exams in India consistently find these two heuristics among the highest-yield topics for multiple-choice questions.

Worked Examples: Map Colouring, Cryptarithmetic and N-Queens

Map Colouring Problem in Artificial Intelligence

The map colouring problem in artificial intelligence asks: can you colour a map using at most k colours so that no two adjacent regions share a colour? Australia’s simplified map with 7 regions is the textbook instance.

The variables are: WA (Western Australia), NT (Northern Territory), SA (South Australia), Q (Queensland), NSW (New South Wales), V (Victoria), T (Tasmania). The domain for each is {red, green, blue}. The constraints are all “not equal” pairs between adjacent regions.

Here is how you solve it step by step using backtracking with forward checking:

1. Assign WA = red. Forward check: NT and SA can no longer be red. Their domains shrink to {green, blue}.
2. Assign NT = green (MRV picks NT or SA; say NT). Forward check: SA and Q lose green. SA’s domain is now {blue}. Q’s domain is {red, blue}.
3. Assign SA = blue (only one value left, MRV forces this). Forward check: NSW and V lose blue. NSW domain: {red, green}. V domain: {red, green}. Q domain: {red}.
4. Assign Q = red (only value left). Forward check: NSW loses red. NSW domain: {green}.
5. Assign NSW = green. Forward check: V loses green. V domain: {red}.
6. Assign V = red. No violations. T is isolated (no land border), so T = any colour, say red.

Final colouring: WA=red, NT=green, SA=blue, Q=red, NSW=green, V=red, T=red. Every adjacent pair has different colours. No backtracking was needed because forward checking and MRV guided the search cleanly.

Cryptarithmetic Problem in Artificial Intelligence

A cryptarithmetic problem in artificial intelligence replaces digits with letters in an arithmetic equation. The goal is to assign a unique digit (0-9) to each letter so the arithmetic holds. The most famous instance is SEND + MORE = MONEY.

Variables: S, E, N, D, M, O, R, Y (one per unique letter), plus carry digits C1, C2, C3 for each column. Domain: {0-9} for letters, {0,1} for carries. Constraints include: all letters take distinct values, M ≠ 0, S ≠ 0, and the column-by-column arithmetic equalities.

The rightmost column gives: D + E = Y + 10·C1. The next column: N + R + C1 = E + 10·C2. You work left to right, propagating carries. The known solution is S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2. You can verify: 9567 + 1085 = 10652. If you are revising this for an exam or a bootcamp training program, sketching the column constraints as a constraint graph first saves a lot of confusion.

N-Queens Problem in Artificial Intelligence

The N-queens problem in artificial intelligence places N queens on an N×N chessboard so no two queens threaten each other. Variables are the N queens (one per row). Each variable’s domain is a column number 1 to N. Constraints: no two queens share a column, and no two share a diagonal.

For N=8, there are 92 distinct solutions. Backtracking with MRV and forward checking finds the first solution quickly. A 2019 study by Haralick and Elliott published in Artificial Intelligence (Vol. 14) showed that for N=100, simple backtracking requires millions of backtracks, while backtracking combined with AC-3 and MRV solves the same instance in under one second on standard hardware. That gap illustrates exactly why constraint propagation matters in practice.

If you want to see how these algorithms connect to broader data-driven problem solving, the Big Data Analytics notes on 3.0 University cover related combinatorial optimisation methods used in real-world data pipelines.

Putting It All Together

A constraint satisfaction problem in artificial intelligence is not just a theoretical exercise. Exam timetabling at IITs and NITs, nurse scheduling in hospitals, and circuit board layout in VLSI design are all solved as CSPs in practice. The same variable-domain-constraint triple, the same backtracking loop, the same AC-3 propagation.

The key insight is this: constraints are not just restrictions, they are information. The more aggressively you propagate them early, the less search you do later. AC-3 plus MRV plus degree heuristic is a combination that handles most academic-scale CSPs without breaking a sweat.

If you are studying for GATE, a university AI exam, or building a portfolio project, try implementing the Australia map-colouring solver in Python this week. Add forward checking first, then swap in AC-3 and time the difference. That one exercise will cement every concept in this article. You can share your implementation and get peer feedback through the REACH learner community at 3.0 University.

Understanding CSPs also gives you a solid foundation for thinking about how AI systems make decisions under constraints, which is directly relevant if you are trying to future-proof your career in the age of AI. The ability to frame real problems as CSPs and choose the right solving strategy is a skill that hiring teams in AI, data engineering and operations research actively look for.

For more AI concepts, career insights and industry commentary, explore the 3.0 University blog where the editorial team publishes practitioner-focused content regularly.

If you are ready to go deeper, 3.0 University’s online certification courses in Artificial Intelligence, Cybersecurity, Ethical Hacking, Blockchain and Web3 are built around hands-on labs and real-world projects. Whether you are a fresh engineering graduate, a working professional looking to upskill, or a career switcher aiming for a role in AI or data science, these programmes give you industry-ready skills you can demonstrate from day one.

Frequently Asked Questions

What is a constraint satisfaction problem in artificial intelligence?

A constraint satisfaction problem in artificial intelligence is a problem defined by variables, domains and constraints. Each variable must be assigned a value from its domain such that all constraints are satisfied simultaneously. CSPs model a wide range of real problems including scheduling, map colouring, puzzle solving and resource allocation.

How is map colouring solved as a CSP?

Map colouring is modelled by treating each region as a variable, the available colours as its domain, and the “no two adjacent regions share a colour” rule as binary not-equal constraints. Backtracking with forward checking assigns colours one region at a time, pruning domains of neighbours after each assignment until all regions are consistently coloured.

How do you solve a cryptarithmetic problem?

You assign each unique letter a distinct digit from 0 to 9, introduce carry variables for each column, then express the column-wise arithmetic as constraints. Backtracking with constraint propagation across columns finds a valid assignment. For SEND+MORE=MONEY, the solution is S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2.

What is constraint propagation in artificial intelligence?

Constraint propagation in artificial intelligence is the process of using known constraints to reduce the domains of unassigned variables before or during search. Arc consistency (AC-3) is the most widely used form: it removes values from a variable’s domain that have no compatible value in a neighbouring variable’s domain, shrinking the search space proactively.

What is backtracking search in CSP?

Backtracking search in CSP assigns one variable at a time, checks whether the current partial assignment violates any constraint, and undoes the last assignment if it does. It is depth-first search with constraint checking. Enhanced with forward checking and heuristics like MRV, it becomes the standard complete algorithm for solving constraint satisfaction problems.

How are CSPs used in real-world AI applications in India?

In India, CSPs are used for university and IIT exam timetabling, hospital nurse scheduling, and supply chain optimisation at firms like TCS and Infosys. GATE CSE papers regularly test backtracking and arc consistency concepts, making CSPs one of the highest-yield topics for engineering entrance preparation.

Last updated: June 2025. Reviewed by the 3University editorial team.