Copyright

Constraint Satisfaction Problems: Definition & Examples

An error occurred trying to load this video.

Try refreshing the page, or contact customer support.

Coming up next: Bayes Networks in Machine Learning: Uses & Examples

You're on a roll. Keep up the good work!

Take Quiz Watch Next Lesson
 Replay
Your next lesson will play in 10 seconds
  • 0:04 Definition
  • 1:53 Popular Problems with CSP
  • 2:33 Converting Process & Example
  • 4:15 Lesson Summary
Save Save Save

Want to watch this again later?

Log in or sign up to add this lesson to a Custom Course.

Log in or Sign up

Timeline
Autoplay
Autoplay
Speed Speed Audio mode
Lesson Transcript
Instructor: Prashant Mishra

Prashant is currently pursuing his bachelors in Computer Science and Engineering.

In this lesson, you will be introduced to the concept of constraint satisfaction problems (CSPs) using real life examples and solutions. We will also discuss how other typical problems can be converted to CSP and solved.

Definition: Constraint Satisfaction Problem

Consider a Sudoku game with some numbers filled initially in some squares. You are expected to fill the empty squares with numbers ranging from 1 to 9 in such a way that no row, column or a block has a number repeating itself. This is a very basic constraint satisfaction problem. You are supposed to solve a problem keeping in mind some constraints. The remaining squares that are to be filled are known as variables, and the range of numbers (1-9) that can fill them is known as a domain. Variables take on values from the domain. The conditions governing how a variable will choose its domain are known as constraints.

A constraint satisfaction problem (CSP) is a problem that requires its solution within some limitations or conditions also known as constraints. It consists of the following:

  • A finite set of variables which stores the solution (V = {V1, V2, V3,....., Vn})
  • A set of discrete values known as domain from which the solution is picked (D = {D1, D2, D3,.....,Dn})
  • A finite set of constraints (C = {C1, C2, C3,......, Cn})

Please note, that the elements in the domain can be both continuous and discrete but in AI, we generally only deal with discrete values.

Also, note that all these sets should be finite except for the domain set. Each variable in the variable set can have different domains. For example, consider the Sudoku problem again. Suppose that a row, column and block already have 3, 5 and 7 filled in. Then the domain for all the variables in that row, column and block will be {1, 2, 4, 6, 8, 9}.

Popular Problems with CSP

The following problems are some of the popular problems that can be solved using CSP:

  1. CryptArithmetic (Coding alphabets to numbers.)
  2. n-Queen (In an n-queen problem, n queens should be placed in an nXn matrix such that no queen shares the same row, column or diagonal.)
  3. Map Coloring (coloring different regions of map, ensuring no adjacent regions have the same color)
  4. Crossword (everyday puzzles appearing in newspapers)
  5. Sudoku (a number grid)
  6. Latin Square Problem

Converting Process & Example

A problem to be converted to CSP requires the following steps:

  • Step 1: Create a variable set.
  • Step 2: Create a domain set.
  • Step 3: Create a constraint set with variables and domains (if possible) after considering the constraints.
  • Step 4: Find an optimal solution.

To unlock this lesson you must be a Study.com Member.
Create your account

Register to view this lesson

Are you a student or a teacher?

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back
What teachers are saying about Study.com
Try it risk-free for 30 days

Earning College Credit

Did you know… We have over 200 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it risk-free for 30 days!
Create an account
Support