Constraint Satisfaction Problem (CSP)

A Constraint Satisfaction Problem is a mathematical problem defined as a state of object that requires the solution with some limitations or conditions also known as constraints. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of research in both Artificial Intelligence (AI) and Operations Research, it consists of 3 different types of values these are: -

1. a finite set of variables which stores the solution (v = {v1 , v2 , v3, …,vn }).
2. a set of discrete values known as domain from which the solution is picked (D = {D1 , D2 , D3 , …Dn }).
3. a finite set of constraints (C = {C1, C2 , C3 , …, Cn }).

Example: Consider you are playing a Sudoku Game, initially some of squares are filled with some numbers range from 0 to 9 and there are some empty squares and you have to fill that empty square in such a way that digits will never be repeat in a row or in a column. This is a very basic Constraint Satisfaction problem. The value range is (0-9) is known as domain and the remaining square are to be filled can be referred as variables. Variables takes from values are known as domain. The condition how a variable will choose from the domain is known as constraints.

There are Some Popular Problems can be solved by using Constraint Satisfaction Problem these are given below:

1. Cryptarithmetic (Coding alphabets to numbers.)
2. n-Queen (In an n-queen problem, n queens should be placed in an (n x n) 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

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc