Working with Constraint Satisfaction Problems, Explained

UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 4.8 Free with a free account

Working with Constraint Satisfaction Problems

Introduction to Artificial Intelligence · Chapter 4: Search, Heuristics, and Game StrategySection 4.8 · lesson 30 of 6913 min · free with a free account

← Pruning Game Trees with Alpha-Beta TechniquesNext lesson: Sequential Decision Making with Markov Processes →

Earn 3 college credits for Introduction to Artificial IntelligenceRecommended for credit by NCCRS · Computer Science 373 · self-paced · one payment, lifetime access
Enroll in Introduction to Artificial Intelligence · $250 →Download the syllabus (PDF)

In this lesson

Solve scheduling, map coloring, and Sudoku with backtracking and constraint propagation.

  • Define a CSP by its variables, domains, and constraints and draw its constraint graph
  • Apply backtracking search with MRV, degree, and least-constraining value heuristics
  • Use forward checking and the AC-3 algorithm to shrink domains
  • Model Sudoku and exam scheduling as constraint satisfaction problems

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,792 words). Read along, or search it.

Opening Examples

Exams, Maps, and Sudoku Share a Structure

Schedule five exams, so no student has two at the same time. Color a map with three colors, so no two neighbors match. Fill in a Sudoku grid. These puzzles look unrelated, yet they share one structure: choose a value for each of several things, while obeying rules about which combinations are allowed. General search treats a problem as a path through states, and never looks inside them. A constraint satisfaction problem, or CSP, exposes the structure instead. Watch how much work that saves.

Definition

Variables, Domains, and Constraints

A CSP has three ingredients. The variables are the things to decide. Each variable has a domain: the set of values it may take. And the constraints are rules that limit which combinations of values are allowed. For map coloring, the variables are the regions, the domain is red, green and blue, and neighbors must differ. For Sudoku, the 81 cells, the digits 1 to 9, and no repeats in a row, column or box. For exams, the exams themselves, the time slots, and exams sharing students at different times. A solution gives every variable a value, and breaks no constraint. A partial assignment that breaks nothing so far is called consistent.

Constraint Types

Unary, Binary, and Higher-Order Constraints

Constraints come in kinds. A unary constraint involves one variable: South must be green. A binary constraint involves two: North and East must differ. A higher-order one involves several: all nine digits in a row are different.

Running Example

Coloring a Five-Region Island

Here's our running example. An island has five regions: Center, North, East, South and West. Center touches all four others, and each outer region touches its two neighbors around the ring. Each region must be painted red, green or blue, neighbors must differ, and South is already green. The constraint graph makes the structure visible: each variable is a node, and each binary constraint is an edge. At a glance, Center has four edges: it's the most constrained. And a region touching no others would be an isolated node, solvable by itself.

Backtracking Search

Assign, Check, and Back Up

Backtracking search builds a solution one variable at a time. Pick an unassigned variable, try a value, and check it against the variables already assigned. If all is well, move on. If a variable has no legal value left, back up to the most recent earlier choice, and try something different. That backing up is the backtracking. Two facts make CSPs special. First, a partial assignment that already breaks a rule is dropped at once, with nothing beyond it explored. Second, the order of assignment doesn't change which solutions exist, only how much effort they take. So the search is free to choose its order wisely.

Worked Example

A Poor Order Hits a Dead End

Here's backtracking on the island with a poor order: North, South, East, West, then Center, trying red, then green, then blue. North is red. South is green, its only legal value. East neighbors red and green, so it's blue. West, by the same reasoning, is also blue. Now Center. Its neighbors already use red, green and blue. Dead end. West, East and South each had only one legal value, so the search backs all the way up and retries North, as green. Then South is green, East is red, West is red, and Center is blue. Solved, but steps one to four were wasted: the dead end only showed up at Center.

Ordering Heuristics

MRV, Degree, and Least-Constraining Value

Three heuristics help. Two choose which variable comes next, and one chooses which value to try first. Minimum remaining values, or MRV, picks the variable with the fewest legal values left. One value means it's forced. None means failure, right away. That's fail first: find problems early, while they're cheap to fix. The degree heuristic breaks ties among MRV choices. It picks the variable in the most constraints with unassigned variables, because it affects the most neighbors. And least-constraining value picks the value that rules out the fewest options for the neighbors. That's succeed first: leave as much freedom as possible.

Worked Example

Least-Constraining Value Picks Green

Here's least-constraining value on the island. South is green, so Center, East and West each have red or blue left. North is still free. Giving North green removes nothing from its neighbors, because green is already gone from them. Red or blue would cut an option from three neighbors. So it tries green.

Quick Check

MRV With a Degree Tie-Breaker

Quick check. Three unassigned variables. X has 2 legal values left, and constraints with 3 unassigned variables. Y has 2 values left, and 1 unassigned neighbor. W has 3 values left, and 4 unassigned neighbors. Using MRV, with the degree heuristic to break ties, which variable comes next? Pause, and decide. X. MRV looks only at values left, so X and Y tie at two, and W, with three, is out. The degree heuristic breaks the tie: X constrains three unassigned variables, Y only one. W is tempting for its four neighbors, but degree only breaks MRV's ties.

Forward Checking

Crossing Off Values From Neighbors

Heuristics steer the search. A second idea, constraint propagation, shrinks the domains, so dead ends are noticed sooner. The simplest form is forward checking. Each time a variable is assigned, remove its value from the domains of its unassigned neighbors. If any neighbor's domain becomes empty, backtrack at once. In Sudoku, it's exactly what you do after writing a 5: cross 5 off the candidates of all 20 cells in the same row, column and box.

Arc Consistency

The AC-3 Procedure

Forward checking only notices an empty domain, so it can miss trouble that's already certain. Arc consistency looks deeper. Two variables joined by a constraint form an arc. The arc from X to Y is consistent, if every value in X's domain has a partner in Y's domain, one that satisfies the constraint. A value with no partner can never be part of a solution, so it's deleted. The AC-3 procedure keeps a queue of arcs. It takes one, and deletes the unsupported values. If that domain changed, it adds back the arcs that point to that variable. It stops when the queue is empty, or a domain is.

Worked Example

AC-3 Solves a Three-Variable Ordering

A small example. P, Q and R each have the domain 1, 2, 3, with P less than Q, and Q less than R. Check P to Q: P equals 3 has no larger Q, so delete it. Check Q to P: Q equals 1 has no smaller P, so delete it. Q to R: Q equals 3 has no larger R. Delete. R to Q: R equals 1 and 2 have no smaller Q left. Delete both. Q's domain changed, so P to Q is checked again. P equals 2 has lost its partner. What's left: P is 1, Q is 2, R is 3. Propagation alone solved this one, with no guessing. That's a bonus, not a guarantee.

Limitation

Arc Consistency Without a Solution

Here's why it's not a guarantee. Three regions all border each other, and only red and blue are available. Every value in every domain still has a partner in each neighbor, so AC-3 removes nothing. Yet no solution exists. Propagation shrinks the search, but a search is still needed to settle the rest.

Comparison

When Each Check Finds the Dead End

The checks catch dead ends at different times. Back to the island, with North red, then South green. Plain backtracking notices only when it reaches Center, after four assignments. Forward checking notices right after East is set blue, when Center's domain empties: three assignments. Arc consistency notices right after South is green. Center, East and West are each down to blue, and Center and East are neighbors: they can't both be blue. Two assignments. The stronger check costs more per step, and often saves much more in search. Running AC-3 after every assignment is a common way to combine them.

Quick Check

Arc Consistency for a Gap of Two

Quick check. X and Y each have the domain 1, 2, 3. The constraint: X is at least Y plus 2. After arc consistency, what's left in each domain? Pause, and predict. X is 3, and Y is 1. X equals 1 or 2 would need Y at most 0, or below, so both go. And Y equals 2 or more would need X to be 4 or more. Gone too. Option B keeps Y equals 2, which has no partner. Option C keeps X equals 2, which has none either. Arc consistency checks both directions.

Combined Approach

Five Assignments With No Backtracking

Now solve the island with MRV, the degree heuristic and forward checking together. South goes first: its domain has just one value, green. Center, East and West lose green. Center comes next. MRV ties at two values, and the degree heuristic favors Center, with three unassigned neighbors. Center is red, so East and West are down to blue. East has one value left, blue, and North loses blue. West is blue. And North has only green left. Five assignments, with no backtracking, against the eight-step trace from before.

Application

Sudoku as a CSP

Sudoku fits exactly. The variables are the 81 cells, and every domain is the digits 1 to 9. A given digit just shrinks a cell's domain to one value. As binary constraints, every cell must differ from its 20 peers: 8 in its row, 8 in its column, and 4 more in its box. Written as one all-different rule for nine cells, it's a higher-order constraint. MRV is how most people solve Sudoku without naming it: find the cell with the fewest possibilities. Forward checking is the crossing off. Subtler cases, like two cells in a box both limited to the same pair of digits, need the box's all-different rule. Checking cells in pairs, as arc consistency does, misses them.

Application

Scheduling Five Exams in Three Slots

Scheduling problems are CSPs in disguise. Five exams, Math, Physics, Chemistry, Art and Music, go into three slots: Monday morning, Monday afternoon, and Tuesday morning. Some students take Math, Physics and Chemistry together, so those three need different slots. Chemistry and Art share students, and so do Art and Music. The Physics lab is closed on Monday morning: a unary constraint. And Art must come before Music: a binary constraint that's an ordering, not a difference. The triangle uses all three slots. One timetable that works: Math Monday morning, Physics Monday afternoon, Chemistry Tuesday morning. Then Art only has to avoid Chemistry's slot, and come before Music: Art Monday morning, Music Monday afternoon.

Key Takeaways

CSP Search and Propagation Summed Up

To sum up. A CSP is variables, domains and constraints, and its constraint graph shows which variables are tied together. Backtracking assigns one variable at a time, and backs up on dead ends. The order changes the effort, not the solutions. MRV and degree pick the most constrained variable first. Least-constraining value tries the value that leaves neighbors the most freedom. Forward checking and AC-3 cross out impossible values, so dead ends show up sooner. Propagation shrinks the search, but doesn't always replace it.

Reflection

Four Volunteers, Three Shifts

Here's something to think about. Four volunteers fill three shifts. Two friends must never share a shift, and one volunteer can't work shift one. What are the variables, the domains and the constraints? And which constraint is unary?

About Introduction to Artificial Intelligence at UPI Study

Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: AI vs Current Trends in CS and IT

Why take it here

Why students take Introduction to Artificial Intelligence with UPI Study

How machines search, reason and learnIntroduction to Artificial Intelligence covers how AI systems are built: intelligent agents, search and heuristics, game strategy, logic, neural networks, machine learning, language and perception, and the ethics of AI. It is a common upper-level course in computer science degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Working with Constraint Satisfaction Problems

What is a constraint satisfaction problem in AI?
A constraint satisfaction problem, or CSP, is a problem defined by variables, a domain of allowed values for each, and constraints limiting which combinations are allowed. A solution gives every variable a value without breaking any constraint. In map coloring, the regions are variables, red, green, and blue form the domain, and neighboring regions must differ. Sudoku and exam scheduling fit the same pattern.
What is the minimum remaining values heuristic?
Minimum remaining values, or MRV, chooses the unassigned variable with the fewest legal values left, so failures show up early while they are cheap to fix. Ties are broken by the degree heuristic, which picks the variable involved in the most constraints with unassigned variables. Once a variable is chosen, least-constraining value tries the value that rules out the fewest options for its neighbors.
What is the difference between forward checking and arc consistency?
Forward checking removes an assigned value from the domains of that variable's unassigned neighbors and backtracks if a domain empties. Arc consistency looks deeper: it deletes any value in one variable's domain that has no supporting partner in a connected variable's domain. Arc consistency therefore catches some dead ends sooner, at a higher cost per step.
Does arc consistency always solve a CSP?
No, arc consistency shrinks domains but does not always find a solution or detect that none exists. Sometimes AC-3 solves a problem outright, as with P less than Q less than R over 1 to 3, which leaves P = 1, Q = 2, R = 3. But three mutually bordering regions with only two colors pass every arc check, yet have no solution, so search is still needed.

About the Introduction to Artificial Intelligence course

How many college credits is Introduction to Artificial Intelligence?
Introduction to Artificial Intelligence (Computer Science 373) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Introduction to Artificial Intelligence cost and what is included?
$250, paid once, with lifetime access: all 69 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Introduction to Artificial Intelligence take?
It is self-paced with no deadlines. The 69 lessons total about 16 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.

69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Introduction to Artificial Intelligence →Download the syllabusEvery course with PRO →
Introduction to Artificial Intelligence
3 credits · NCCRSEnroll →