Siksha Sarovar

Siksha Sarovar (sikshasarovar.com) is a free educational web application that helps students in India learn programming and prepare for academic and competitive exams. The platform offers structured coding courses (C, C++, Python, Java, HTML, CSS, PHP, Power BI, AI, Machine Learning, Data Science), complete university curriculum notes for BCA/MCA students with previous year question papers, Class 10 and Class 12 CBSE/HBSE school notes, and dedicated preparation material for SSC, UPSC, Banking, Railway and other government exams. Browsing the site is completely free and requires no account. Users may optionally sign in with Google solely to save their learning progress, quiz scores and personal preferences across devices.

Privacy Policy | Terms of Service | Contact Siksha Sarovar | About Siksha Sarovar

v4.0.9 · PWA
Siksha Sarovar logo
Siksha Sarovar
Your Learning Universe

Siksha Sarovar is a free e-learning platform for coding courses, BCA university notes and competitive exam preparation. Optional Google sign-in saves your learning progress across devices.

Initializing knowledge base…
Compiling modules 0%

Unit 1 — Constraint Satisfaction

Lesson 14 of 34 in the free Artificial Intelligence notes on Siksha Sarovar, written by Rohit Jangra.

Constraint Satisfaction

A Constraint Satisfaction Problem (CSP) asks for an assignment of values to a set of variables such that every constraint on those variables is satisfied. Unlike ordinary state-space search (which searches for a path), CSP search looks for a complete, consistent assignment — the path taken to reach it doesn't matter.

Formal Definition

A CSP consists of:

ComponentMeaning
VariablesX1, X2, ..., Xn — the things to be assigned values
DomainsD1, D2, ..., Dn — the set of legal values for each variable
ConstraintsRules restricting which combinations of values are allowed

Worked Example: Map Colouring

Colour a map of regions so that no two adjacent regions share a colour, using the fewest colours possible.

  • Variables: regions A, B, C, D
  • Domain: {Red, Green, Blue} for each region
  • Constraints: adjacent regions must have different colours (A≠B, A≠C, B≠C, B≠D, C≠D)

One valid solution: A=Red, B=Green, C=Blue, D=Red.

Worked Example: Cryptarithmetic Revisited

SEND + MORE = MONEY is also a CSP: variables are the letters, domain is {0..9}, and constraints are "all-different" plus the column-wise arithmetic equations (with carries).

Solving CSPs

TechniqueIdea
Backtracking searchAssign variables one at a time; if a partial assignment violates a constraint, backtrack and try a different value
Constraint propagationUse constraints to eliminate values from other variables' domains before searching (e.g., arc consistency) — shrinks the search space
Most-constrained-variable heuristicAssign the variable with the fewest remaining legal values first — fails fast if the branch is doomed
Least-constraining-value heuristicWhen choosing a value, prefer the one that rules out the fewest values for neighbouring variables

CSP vs Ordinary Heuristic Search

Ordinary search (hill climbing / A*)CSP
Looking forA path from start to goalA consistent value assignment
StatePartial path so farPartial assignment of variables
"Goal test"Reached a designated goal stateAll variables assigned, no constraint violated
Typical usePuzzle-solving, route findingScheduling, timetabling, map colouring, Sudoku

Exam tip: CSP questions frequently ask you to formulate a problem (identify variables, domains, constraints) — practice this formulation step, since it is usually worth more marks than the solving algorithm itself.