Constraint Satisfaction Problems (CSP) in Artificial Intelligence

Finding a solution that meets a set of constraints is the goal of constraint satisfaction problems (CSPs), a type of AI issue. Finding values for a group of variables that fulfill a set of restrictions or rules is the aim of constraint satisfaction problems. For tasks including resource allocation, planning, scheduling, and decision-making, CSPs are frequently employed in AI.

There are mainly three basic components in the constraint satisfaction problem:

Variables: The things that need to be determined are variables. Variables in a CSP are the objects that must have values assigned to them in order to satisfy a particular set of constraints. Boolean, integer, and categorical variables are just a few examples of the various types of variables, for instance, could stand in for the many puzzle cells that need to be filled with numbers in a sudoku puzzle.

Domains: The range of potential values that a variable can have is represented by domains. Depending on the issue, a domain may be finite or limitless. For instance, in Sudoku, the set of numbers from 1 to 9 can serve as the domain of a variable representing a problem cell.

Constraints: The guidelines that control how variables relate to one another are known as constraints. Constraints in a CSP define the ranges of possible values for variables. Unary constraints, binary constraints, and higher-order constraints are only a few examples of the various sorts of constraints. For instance, in a sudoku problem, the restrictions might be that each row, column, and 3×3 box can only have one instance of each number from 1 to 9.

Constraint Satisfaction Problems (CSP) representation:

• The finite set of variables V ₁ , V ₂ , V ₃ ……………..V _n .
• Non-empty domain for every single variable D ₁ , D ₂ , D ₃ …………..D _n .
• The finite set of constraints C ₁ , C ₂ …….…, Cm.
  • where each constraint C _i restricts the possible values for variables,
    • e.g., V ₁ ≠ V ₂
    • Example: <(V ₁ , V ₂ ), V ₁ not equal to V ₂ >
    • There might be a clear list of permitted combinations. Perhaps a relation that is abstract and that allows for membership testing and listing.

    Constraint Satisfaction Problems (CSP) algorithms:

    • The backtracking algorithm is a depth-first search algorithm that methodically investigates the search space of potential solutions up until a solution is discovered that satisfies all the restrictions. The method begins by choosing a variable and giving it a value before repeatedly attempting to give values to the other variables. The method returns to the prior variable and tries a different value if at any time a variable cannot be given a value that fulfills the requirements. Once all assignments have been tried or a solution that satisfies all constraints has been discovered, the algorithm ends.
    • The forward-checking algorithm is a variation of the backtracking algorithm that condenses the search space using a type of local consistency. For each unassigned variable, the method keeps a list of remaining values and applies local constraints to eliminate inconsistent values from these sets. The algorithm examines a variable’s neighbors after it is given a value to see whether any of its remaining values become inconsistent and removes them from the sets if they do. The algorithm goes backward if, after forward checking, a variable has no more values.
    • Algorithms for propagating constraints are a class that uses local consistency and inference to condense the search space. These algorithms operate by propagating restrictions between variables and removing inconsistent values from the variable domains using the information obtained.

    Implementations code for Constraint Satisfaction Problems (CSP):

    Implement Constraint Satisfaction Problems algorithms with code

    Define the Problem

    Here we are solving Sudoku Puzzle with Constraint Satisfaction Problems algorithms

    Output:

    5 3 0 | 0 7 0 | 0 0 0 
    6 0 0 | 1 9 5 | 0 0 0 
    0 9 8 | 0 0 0 | 0 6 0 
    - - - - - - - - - - - 
    8 0 0 | 0 6 0 | 0 0 3 
    4 0 0 | 8 0 3 | 0 0 1 
    7 0 0 | 0 2 0 | 0 0 6 
    - - - - - - - - - - - 
    0 6 0 | 0 0 0 | 2 8 0 
    0 0 0 | 4 1 9 | 0 0 5 
    0 0 0 | 0 8 0 | 0 0 0 

    Define Variables for the Constraint Satisfaction Problem

    Output :

    [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), 
    (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), 
    (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), 
    (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), 
    (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (4, 7), (4, 8), 
    (5, 0), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8), 
    (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (6, 7), (6, 8), 
    (7, 0), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 6), (7, 7), (7, 8), 
    (8, 0), (8, 1), (8, 2), (8, 3), (8, 4), (8, 5), (8, 6), (8, 7), (8, 8)]

    Define the Domains for Constraint Satisfaction Problem

    Output :

    <(0, 0): ,
     (0, 1): ,
     (0, 2): ,
     (0, 3): ,
     (0, 4): ,
     (0, 5): ,
     (0, 6): ,
     (0, 7): ,
     (0, 8): ,
     (1, 0): ,
     (1, 1): ,
     (1, 2): ,
     (1, 3): ,
     (1, 4): ,
     (1, 5): ,
     (1, 6): ,
     (1, 7): ,
     (1, 8): ,
     (2, 0): ,
     (2, 1): ,
     (2, 2): ,
     (2, 3): ,
     (2, 4): ,
     (2, 5): ,
     (2, 6): ,
     (2, 7): ,
     (2, 8): ,
     (3, 0): ,
     (3, 1): ,
     (3, 2): ,
     (3, 3): ,
     (3, 4): ,
     (3, 5): ,
     (3, 6): ,
     (3, 7): ,
     (3, 8): ,
     (4, 0): ,
     (4, 1): ,
     (4, 2): ,
     (4, 3): ,
     (4, 4): ,
     (4, 5): ,
     (4, 6): ,
     (4, 7): ,
     (4, 8): ,
     (5, 0): ,
     (5, 1): ,
     (5, 2): ,
     (5, 3): ,
     (5, 4): ,
     (5, 5): ,
     (5, 6): ,
     (5, 7): ,
     (5, 8): ,
     (6, 0): ,
     (6, 1): ,
     (6, 2): ,
     (6, 3): ,
     (6, 4): ,
     (6, 5): ,
     (6, 6): ,
     (6, 7): ,
     (6, 8): ,
     (7, 0): ,
     (7, 1): ,
     (7, 2): ,
     (7, 3): ,
     (7, 4): ,
     (7, 5): ,
     (7, 6): ,
     (7, 7): ,
     (7, 8): ,
     (8, 0): ,
     (8, 1): ,
     (8, 2): ,
     (8, 3): ,
     (8, 4): ,
     (8, 5): ,
     (8, 6): ,
     (8, 7): ,
     (8, 8): >

    Define the Constraint for Constraint Satisfaction Problem

    Output :

    <(0, 0): [(1, 0), (0, 1), (2, 0), (0, 2), (3, 0), (0, 3), (4, 0), (0, 4), (5, 0), (0, 5), (6, 0), (0, 6), (7, 0), (0, 7), (8, 0), (0, 8), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)], (0, 1): [(0, 0), (1, 1), (2, 1), (0, 2), (3, 1), (0, 3), (4, 1), (0, 4), (5, 1), (0, 5), (6, 1), (0, 6), (7, 1), (0, 7), (8, 1), (0, 8), (0, 0), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)], (0, 2): [(0, 0), (1, 2), (0, 1), (2, 2), (3, 2), (0, 3), (4, 2), (0, 4), (5, 2), (0, 5), (6, 2), (0, 6), (7, 2), (0, 7), (8, 2), (0, 8), (0, 0), (0, 1), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)], (0, 3): [(0, 0), (1, 3), (0, 1), (2, 3), (0, 2), (3, 3), (4, 3), (0, 4), (5, 3), (0, 5), (6, 3), (0, 6), (7, 3), (0, 7), (8, 3), (0, 8), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)], (0, 4): [(0, 0), (1, 4), (0, 1), (2, 4), (0, 2), (3, 4), (0, 3), (4, 4), (5, 4), (0, 5), (6, 4), (0, 6), (7, 4), (0, 7), (8, 4), (0, 8), (0, 3), (0, 5), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)], (0, 5): [(0, 0), (1, 5), (0, 1), (2, 5), (0, 2), (3, 5), (0, 3), (4, 5), (0, 4), (5, 5), (6, 5), (0, 6), (7, 5), (0, 7), (8, 5), (0, 8), (0, 3), (0, 4), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)], (0, 6): [(0, 0), (1, 6), (0, 1), (2, 6), (0, 2), (3, 6), (0, 3), (4, 6), (0, 4), (5, 6), (0, 5), (6, 6), (7, 6), (0, 7), (8, 6), (0, 8), (0, 7), (0, 8), (1, 6), (1, 7), (1, 8), (2, 6), (2, 7), (2, 8)], (0, 7): [(0, 0), (1, 7), (0, 1), (2, 7), (0, 2), (3, 7), (0, 3), (4, 7), (0, 4), (5, 7), (0, 5), (6, 7), (0, 6), (7, 7), (8, 7), (0, 8), (0, 6), (0, 8), (1, 6), (1, 7), (1, 8), (2, 6), (2, 7), (2, 8)], (0, 8): [(0, 0), (1, 8), (0, 1), (2, 8), (0, 2), (3, 8), (0, 3), (4, 8), (0, 4), (5, 8), (0, 5), (6, 8), (0, 6), (7, 8), (0, 7), (8, 8), (0, 6), (0, 7), (1, 6), (1, 7), (1, 8), (2, 6), (2, 7), (2, 8)], 
    (1, 0): [(0, 0), (1, 1), (2, 0), (1, 2), (3, 0), (1, 3), (4, 0), (1, 4), (5, 0), (1, 5), (6, 0), (1, 6), (7, 0), (1, 7), (8, 0), (1, 8), (0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)], (1, 1): [(0, 1), (1, 0), (2, 1), (1, 2), (3, 1), (1, 3), (4, 1), (1, 4), (5, 1), (1, 5), (6, 1), (1, 6), (7, 1), (1, 7), (8, 1), (1, 8), (0, 0), (0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1), (2, 2)], (1, 2): [(0, 2), (1, 0), (1, 1), (2, 2), (3, 2), (1, 3), (4, 2), (1, 4), (5, 2), (1, 5), (6, 2), (1, 6), (7, 2), (1, 7), (8, 2), (1, 8), (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0), (2, 1), (2, 2)], (1, 3): [(0, 3), (1, 0), (1, 1), (2, 3), (1, 2), (3, 3), (4, 3), (1, 4), (5, 3), (1, 5), (6, 3), (1, 6), (7, 3), (1, 7), (8, 3), (1, 8), (0, 3), (0, 4), (0, 5), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)], (1, 4): [(0, 4), (1, 0), (1, 1), (2, 4), (1, 2), (3, 4), (1, 3), (4, 4), (5, 4), (1, 5), (6, 4), (1, 6), (7, 4), (1, 7), (8, 4), (1, 8), (0, 3), (0, 4), (0, 5), (1, 3), (1, 5), (2, 3), (2, 4), (2, 5)], (1, 5): [(0, 5), (1, 0), (1, 1), (2, 5), (1, 2), (3, 5), (1, 3), (4, 5), (1, 4), (5, 5), (6, 5), (1, 6), (7, 5), (1, 7), (8, 5), (1, 8), (0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (2, 3), (2, 4), (2, 5)], (1, 6): [(0, 6), (1, 0), (1, 1), (2, 6), (1, 2), (3, 6), (1, 3), (4, 6), (1, 4), (5, 6), (1, 5), (6, 6), (7, 6), (1, 7), (8, 6), (1, 8), (0, 6), (0, 7), (0, 8), (1, 7), (1, 8), (2, 6), (2, 7), (2, 8)], (1, 7): [(0, 7), (1, 0), (1, 1), (2, 7), (1, 2), (3, 7), (1, 3), (4, 7), (1, 4), (5, 7), (1, 5), (6, 7), (1, 6), (7, 7), (8, 7), (1, 8), (0, 6), (0, 7), (0, 8), (1, 6), (1, 8), (2, 6), (2, 7), (2, 8)], (1, 8): [(0, 8), (1, 0), (1, 1), (2, 8), (1, 2), (3, 8), (1, 3), (4, 8), (1, 4), (5, 8), (1, 5), (6, 8), (1, 6), (7, 8), (1, 7), (8, 8), (0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (2, 6), (2, 7), (2, 8)], 
    (2, 0): [(0, 0), (1, 0), (2, 1), (2, 2), (3, 0), (2, 3), (4, 0), (2, 4), (5, 0), (2, 5), (6, 0), (2, 6), (7, 0), (2, 7), (8, 0), (2, 8), (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 1), (2, 2)], (2, 1): [(0, 1), (2, 0), (1, 1), (2, 2), (3, 1), (2, 3), (4, 1), (2, 4), (5, 1), (2, 5), (6, 1), (2, 6), (7, 1), (2, 7), (8, 1), (2, 8), (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 2)], (2, 2): [(0, 2), (2, 0), (1, 2), (2, 1), (3, 2), (2, 3), (4, 2), (2, 4), (5, 2), (2, 5), (6, 2), (2, 6), (7, 2), (2, 7), (8, 2), (2, 8), (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1)], (2, 3): [(0, 3), (2, 0), (1, 3), (2, 1), (2, 2), (3, 3), (4, 3), (2, 4), (5, 3), (2, 5), (6, 3), (2, 6), (7, 3), (2, 7), (8, 3), (2, 8), (0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (2, 4), (2, 5)], (2, 4): [(0, 4), (2, 0), (1, 4), (2, 1), (2, 2), (3, 4), (2, 3), (4, 4), (5, 4), (2, 5), (6, 4), (2, 6), (7, 4), (2, 7), (8, 4), (2, 8), (0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5)], (2, 5): [(0, 5), (2, 0), (1, 5), (2, 1), (2, 2), (3, 5), (2, 3), (4, 5), (2, 4), (5, 5), (6, 5), (2, 6), (7, 5), (2, 7), (8, 5), (2, 8), (0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4)], (2, 6): [(0, 6), (2, 0), (1, 6), (2, 1), (2, 2), (3, 6), (2, 3), (4, 6), (2, 4), (5, 6), (2, 5), (6, 6), (7, 6), (2, 7), (8, 6), (2, 8), (0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (1, 8), (2, 7), (2, 8)], (2, 7): [(0, 7), (2, 0), (1, 7), (2, 1), (2, 2), (3, 7), (2, 3), (4, 7), (2, 4), (5, 7), (2, 5), (6, 7), (2, 6), (7, 7), (8, 7), (2, 8), (0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (1, 8), (2, 6), (2, 8)], (2, 8): [(0, 8), (2, 0), (1, 8), (2, 1), (2, 2), (3, 8), (2, 3), (4, 8), (2, 4), (5, 8), (2, 5), (6, 8), (2, 6), (7, 8), (2, 7), (8, 8), (0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (1, 8), (2, 6), (2, 7)], 
    (3, 0): [(0, 0), (1, 0), (3, 1), (2, 0), (3, 2), (3, 3), (4, 0), (3, 4), (5, 0), (3, 5), (6, 0), (3, 6), (7, 0), (3, 7), (8, 0), (3, 8), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (5, 0), (5, 1), (5, 2)], (3, 1): [(0, 1), (3, 0), (1, 1), (2, 1), (3, 2), (3, 3), (4, 1), (3, 4), (5, 1), (3, 5), (6, 1), (3, 6), (7, 1), (3, 7), (8, 1), (3, 8), (3, 0), (3, 2), (4, 0), (4, 1), (4, 2), (5, 0), (5, 1), (5, 2)], (3, 2): [(0, 2), (3, 0), (1, 2), (3, 1), (2, 2), (3, 3), (4, 2), (3, 4), (5, 2), (3, 5), (6, 2), (3, 6), (7, 2), (3, 7), (8, 2), (3, 8), (3, 0), (3, 1), (4, 0), (4, 1), (4, 2), (5, 0), (5, 1), (5, 2)], (3, 3): [(0, 3), (3, 0), (1, 3), (3, 1), (2, 3), (3, 2), (4, 3), (3, 4), (5, 3), (3, 5), (6, 3), (3, 6), (7, 3), (3, 7), (8, 3), (3, 8), (3, 4), (3, 5), (4, 3), (4, 4), (4, 5), (5, 3), (5, 4), (5, 5)], (3, 4): [(0, 4), (3, 0), (1, 4), (3, 1), (2, 4), (3, 2), (3, 3), (4, 4), (5, 4), (3, 5), (6, 4), (3, 6), (7, 4), (3, 7), (8, 4), (3, 8), (3, 3), (3, 5), (4, 3), (4, 4), (4, 5), (5, 3), (5, 4), (5, 5)], (3, 5): [(0, 5), (3, 0), (1, 5), (3, 1), (2, 5), (3, 2), (3, 3), (4, 5), (3, 4), (5, 5), (6, 5), (3, 6), (7, 5), (3, 7), (8, 5), (3, 8), (3, 3), (3, 4), (4, 3), (4, 4), (4, 5), (5, 3), (5, 4), (5, 5)], (3, 6): [(0, 6), (3, 0), (1, 6), (3, 1), (2, 6), (3, 2), (3, 3), (4, 6), (3, 4), (5, 6), (3, 5), (6, 6), (7, 6), (3, 7), (8, 6), (3, 8), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8)], (3, 7): [(0, 7), (3, 0), (1, 7), (3, 1), (2, 7), (3, 2), (3, 3), (4, 7), (3, 4), (5, 7), (3, 5), (6, 7), (3, 6), (7, 7), (8, 7), (3, 8), (3, 6), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8)], (3, 8): [(0, 8), (3, 0), (1, 8), (3, 1), (2, 8), (3, 2), (3, 3), (4, 8), (3, 4), (5, 8), (3, 5), (6, 8), (3, 6), (7, 8), (3, 7), (8, 8), (3, 6), (3, 7), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8)], 
    (4, 0): [(0, 0), (1, 0), (4, 1), (2, 0), (4, 2), (3, 0), (4, 3), (4, 4), (5, 0), (4, 5), (6, 0), (4, 6), (7, 0), (4, 7), (8, 0), (4, 8), (3, 0), (3, 1), (3, 2), (4, 1), (4, 2), (5, 0), (5, 1), (5, 2)], (4, 1): [(0, 1), (4, 0), (1, 1), (2, 1), (4, 2), (3, 1), (4, 3), (4, 4), (5, 1), (4, 5), (6, 1), (4, 6), (7, 1), (4, 7), (8, 1), (4, 8), (3, 0), (3, 1), (3, 2), (4, 0), (4, 2), (5, 0), (5, 1), (5, 2)], (4, 2): [(0, 2), (4, 0), (1, 2), (4, 1), (2, 2), (3, 2), (4, 3), (4, 4), (5, 2), (4, 5), (6, 2), (4, 6), (7, 2), (4, 7), (8, 2), (4, 8), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (5, 0), (5, 1), (5, 2)], (4, 3): [(0, 3), (4, 0), (1, 3), (4, 1), (2, 3), (4, 2), (3, 3), (4, 4), (5, 3), (4, 5), (6, 3), (4, 6), (7, 3), (4, 7), (8, 3), (4, 8), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5), (5, 3), (5, 4), (5, 5)], (4, 4): [(0, 4), (4, 0), (1, 4), (4, 1), (2, 4), (4, 2), (3, 4), (4, 3), (5, 4), (4, 5), (6, 4), (4, 6), (7, 4), (4, 7), (8, 4), (4, 8), (3, 3), (3, 4), (3, 5), (4, 3), (4, 5), (5, 3), (5, 4), (5, 5)], (4, 5): [(0, 5), (4, 0), (1, 5), (4, 1), (2, 5), (4, 2), (3, 5), (4, 3), (4, 4), (5, 5), (6, 5), (4, 6), (7, 5), (4, 7), (8, 5), (4, 8), (3, 3), (3, 4), (3, 5), (4, 3), (4, 4), (5, 3), (5, 4), (5, 5)], (4, 6): [(0, 6), (4, 0), (1, 6), (4, 1), (2, 6), (4, 2), (3, 6), (4, 3), (4, 4), (5, 6), (4, 5), (6, 6), (7, 6), (4, 7), (8, 6), (4, 8), (3, 6), (3, 7), (3, 8), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8)], (4, 7): [(0, 7), (4, 0), (1, 7), (4, 1), (2, 7), (4, 2), (3, 7), (4, 3), (4, 4), (5, 7), (4, 5), (6, 7), (4, 6), (7, 7), (8, 7), (4, 8), (3, 6), (3, 7), (3, 8), (4, 6), (4, 8), (5, 6), (5, 7), (5, 8)], (4, 8): [(0, 8), (4, 0), (1, 8), (4, 1), (2, 8), (4, 2), (3, 8), (4, 3), (4, 4), (5, 8), (4, 5), (6, 8), (4, 6), (7, 8), (4, 7), (8, 8), (3, 6), (3, 7), (3, 8), (4, 6), (4, 7), (5, 6), (5, 7), (5, 8)], 
    (5, 0): [(0, 0), (1, 0), (5, 1), (2, 0), (5, 2), (3, 0), (5, 3), (4, 0), (5, 4), (5, 5), (6, 0), (5, 6), (7, 0), (5, 7), (8, 0), (5, 8), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (5, 1), (5, 2)], (5, 1): [(0, 1), (5, 0), (1, 1), (2, 1), (5, 2), (3, 1), (5, 3), (4, 1), (5, 4), (5, 5), (6, 1), (5, 6), (7, 1), (5, 7), (8, 1), (5, 8), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (5, 0), (5, 2)], (5, 2): [(0, 2), (5, 0), (1, 2), (5, 1), (2, 2), (3, 2), (5, 3), (4, 2), (5, 4), (5, 5), (6, 2), (5, 6), (7, 2), (5, 7), (8, 2), (5, 8), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (5, 0), (5, 1)], (5, 3): [(0, 3), (5, 0), (1, 3), (5, 1), (2, 3), (5, 2), (3, 3), (4, 3), (5, 4), (5, 5), (6, 3), (5, 6), (7, 3), (5, 7), (8, 3), (5, 8), (3, 3), (3, 4), (3, 5), (4, 3), (4, 4), (4, 5), (5, 4), (5, 5)], (5, 4): [(0, 4), (5, 0), (1, 4), (5, 1), (2, 4), (5, 2), (3, 4), (5, 3), (4, 4), (5, 5), (6, 4), (5, 6), (7, 4), (5, 7), (8, 4), (5, 8), (3, 3), (3, 4), (3, 5), (4, 3), (4, 4), (4, 5), (5, 3), (5, 5)], (5, 5): [(0, 5), (5, 0), (1, 5), (5, 1), (2, 5), (5, 2), (3, 5), (5, 3), (4, 5), (5, 4), (6, 5), (5, 6), (7, 5), (5, 7), (8, 5), (5, 8), (3, 3), (3, 4), (3, 5), (4, 3), (4, 4), (4, 5), (5, 3), (5, 4)], (5, 6): [(0, 6), (5, 0), (1, 6), (5, 1), (2, 6), (5, 2), (3, 6), (5, 3), (4, 6), (5, 4), (5, 5), (6, 6), (7, 6), (5, 7), (8, 6), (5, 8), (3, 6), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 7), (5, 8)], (5, 7): [(0, 7), (5, 0), (1, 7), (5, 1), (2, 7), (5, 2), (3, 7), (5, 3), (4, 7), (5, 4), (5, 5), (6, 7), (5, 6), (7, 7), (8, 7), (5, 8), (3, 6), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 8)], (5, 8): [(0, 8), (5, 0), (1, 8), (5, 1), (2, 8), (5, 2), (3, 8), (5, 3), (4, 8), (5, 4), (5, 5), (6, 8), (5, 6), (7, 8), (5, 7), (8, 8), (3, 6), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7)], 
    (6, 0): [(0, 0), (1, 0), (6, 1), (2, 0), (6, 2), (3, 0), (6, 3), (4, 0), (6, 4), (5, 0), (6, 5), (6, 6), (7, 0), (6, 7), (8, 0), (6, 8), (6, 1), (6, 2), (7, 0), (7, 1), (7, 2), (8, 0), (8, 1), (8, 2)], (6, 1): [(0, 1), (6, 0), (1, 1), (2, 1), (6, 2), (3, 1), (6, 3), (4, 1), (6, 4), (5, 1), (6, 5), (6, 6), (7, 1), (6, 7), (8, 1), (6, 8), (6, 0), (6, 2), (7, 0), (7, 1), (7, 2), (8, 0), (8, 1), (8, 2)], (6, 2): [(0, 2), (6, 0), (1, 2), (6, 1), (2, 2), (3, 2), (6, 3), (4, 2), (6, 4), (5, 2), (6, 5), (6, 6), (7, 2), (6, 7), (8, 2), (6, 8), (6, 0), (6, 1), (7, 0), (7, 1), (7, 2), (8, 0), (8, 1), (8, 2)], (6, 3): [(0, 3), (6, 0), (1, 3), (6, 1), (2, 3), (6, 2), (3, 3), (4, 3), (6, 4), (5, 3), (6, 5), (6, 6), (7, 3), (6, 7), (8, 3), (6, 8), (6, 4), (6, 5), (7, 3), (7, 4), (7, 5), (8, 3), (8, 4), (8, 5)], (6, 4): [(0, 4), (6, 0), (1, 4), (6, 1), (2, 4), (6, 2), (3, 4), (6, 3), (4, 4), (5, 4), (6, 5), (6, 6), (7, 4), (6, 7), (8, 4), (6, 8), (6, 3), (6, 5), (7, 3), (7, 4), (7, 5), (8, 3), (8, 4), (8, 5)], (6, 5): [(0, 5), (6, 0), (1, 5), (6, 1), (2, 5), (6, 2), (3, 5), (6, 3), (4, 5), (6, 4), (5, 5), (6, 6), (7, 5), (6, 7), (8, 5), (6, 8), (6, 3), (6, 4), (7, 3), (7, 4), (7, 5), (8, 3), (8, 4), (8, 5)], (6, 6): [(0, 6), (6, 0), (1, 6), (6, 1), (2, 6), (6, 2), (3, 6), (6, 3), (4, 6), (6, 4), (5, 6), (6, 5), (7, 6), (6, 7), (8, 6), (6, 8), (6, 7), (6, 8), (7, 6), (7, 7), (7, 8), (8, 6), (8, 7), (8, 8)], (6, 7): [(0, 7), (6, 0), (1, 7), (6, 1), (2, 7), (6, 2), (3, 7), (6, 3), (4, 7), (6, 4), (5, 7), (6, 5), (6, 6), (7, 7), (8, 7), (6, 8), (6, 6), (6, 8), (7, 6), (7, 7), (7, 8), (8, 6), (8, 7), (8, 8)], (6, 8): [(0, 8), (6, 0), (1, 8), (6, 1), (2, 8), (6, 2), (3, 8), (6, 3), (4, 8), (6, 4), (5, 8), (6, 5), (6, 6), (7, 8), (6, 7), (8, 8), (6, 6), (6, 7), (7, 6), (7, 7), (7, 8), (8, 6), (8, 7), (8, 8)], 
    (7, 0): [(0, 0), (1, 0), (7, 1), (2, 0), (7, 2), (3, 0), (7, 3), (4, 0), (7, 4), (5, 0), (7, 5), (6, 0), (7, 6), (7, 7), (8, 0), (7, 8), (6, 0), (6, 1), (6, 2), (7, 1), (7, 2), (8, 0), (8, 1), (8, 2)], (7, 1): [(0, 1), (7, 0), (1, 1), (2, 1), (7, 2), (3, 1), (7, 3), (4, 1), (7, 4), (5, 1), (7, 5), (6, 1), (7, 6), (7, 7), (8, 1), (7, 8), (6, 0), (6, 1), (6, 2), (7, 0), (7, 2), (8, 0), (8, 1), (8, 2)], (7, 2): [(0, 2), (7, 0), (1, 2), (7, 1), (2, 2), (3, 2), (7, 3), (4, 2), (7, 4), (5, 2), (7, 5), (6, 2), (7, 6), (7, 7), (8, 2), (7, 8), (6, 0), (6, 1), (6, 2), (7, 0), (7, 1), (8, 0), (8, 1), (8, 2)], (7, 3): [(0, 3), (7, 0), (1, 3), (7, 1), (2, 3), (7, 2), (3, 3), (4, 3), (7, 4), (5, 3), (7, 5), (6, 3), (7, 6), (7, 7), (8, 3), (7, 8), (6, 3), (6, 4), (6, 5), (7, 4), (7, 5), (8, 3), (8, 4), (8, 5)], (7, 4): [(0, 4), (7, 0), (1, 4), (7, 1), (2, 4), (7, 2), (3, 4), (7, 3), (4, 4), (5, 4), (7, 5), (6, 4), (7, 6), (7, 7), (8, 4), (7, 8), (6, 3), (6, 4), (6, 5), (7, 3), (7, 5), (8, 3), (8, 4), (8, 5)], (7, 5): [(0, 5), (7, 0), (1, 5), (7, 1), (2, 5), (7, 2), (3, 5), (7, 3), (4, 5), (7, 4), (5, 5), (6, 5), (7, 6), (7, 7), (8, 5), (7, 8), (6, 3), (6, 4), (6, 5), (7, 3), (7, 4), (8, 3), (8, 4), (8, 5)], (7, 6): [(0, 6), (7, 0), (1, 6), (7, 1), (2, 6), (7, 2), (3, 6), (7, 3), (4, 6), (7, 4), (5, 6), (7, 5), (6, 6), (7, 7), (8, 6), (7, 8), (6, 6), (6, 7), (6, 8), (7, 7), (7, 8), (8, 6), (8, 7), (8, 8)], (7, 7): [(0, 7), (7, 0), (1, 7), (7, 1), (2, 7), (7, 2), (3, 7), (7, 3), (4, 7), (7, 4), (5, 7), (7, 5), (6, 7), (7, 6), (8, 7), (7, 8), (6, 6), (6, 7), (6, 8), (7, 6), (7, 8), (8, 6), (8, 7), (8, 8)], (7, 8): [(0, 8), (7, 0), (1, 8), (7, 1), (2, 8), (7, 2), (3, 8), (7, 3), (4, 8), (7, 4), (5, 8), (7, 5), (6, 8), (7, 6), (7, 7), (8, 8), (6, 6), (6, 7), (6, 8), (7, 6), (7, 7), (8, 6), (8, 7), (8, 8)], 
    (8, 0): [(0, 0), (1, 0), (8, 1), (2, 0), (8, 2), (3, 0), (8, 3), (4, 0), (8, 4), (5, 0), (8, 5), (6, 0), (8, 6), (7, 0), (8, 7), (8, 8), (6, 0), (6, 1), (6, 2), (7, 0), (7, 1), (7, 2), (8, 1), (8, 2)], (8, 1): [(0, 1), (8, 0), (1, 1), (2, 1), (8, 2), (3, 1), (8, 3), (4, 1), (8, 4), (5, 1), (8, 5), (6, 1), (8, 6), (7, 1), (8, 7), (8, 8), (6, 0), (6, 1), (6, 2), (7, 0), (7, 1), (7, 2), (8, 0), (8, 2)], (8, 2): [(0, 2), (8, 0), (1, 2), (8, 1), (2, 2), (3, 2), (8, 3), (4, 2), (8, 4), (5, 2), (8, 5), (6, 2), (8, 6), (7, 2), (8, 7), (8, 8), (6, 0), (6, 1), (6, 2), (7, 0), (7, 1), (7, 2), (8, 0), (8, 1)], (8, 3): [(0, 3), (8, 0), (1, 3), (8, 1), (2, 3), (8, 2), (3, 3), (4, 3), (8, 4), (5, 3), (8, 5), (6, 3), (8, 6), (7, 3), (8, 7), (8, 8), (6, 3), (6, 4), (6, 5), (7, 3), (7, 4), (7, 5), (8, 4), (8, 5)], (8, 4): [(0, 4), (8, 0), (1, 4), (8, 1), (2, 4), (8, 2), (3, 4), (8, 3), (4, 4), (5, 4), (8, 5), (6, 4), (8, 6), (7, 4), (8, 7), (8, 8), (6, 3), (6, 4), (6, 5), (7, 3), (7, 4), (7, 5), (8, 3), (8, 5)], (8, 5): [(0, 5), (8, 0), (1, 5), (8, 1), (2, 5), (8, 2), (3, 5), (8, 3), (4, 5), (8, 4), (5, 5), (6, 5), (8, 6), (7, 5), (8, 7), (8, 8), (6, 3), (6, 4), (6, 5), (7, 3), (7, 4), (7, 5), (8, 3), (8, 4)], (8, 6): [(0, 6), (8, 0), (1, 6), (8, 1), (2, 6), (8, 2), (3, 6), (8, 3), (4, 6), (8, 4), (5, 6), (8, 5), (6, 6), (7, 6), (8, 7), (8, 8), (6, 6), (6, 7), (6, 8), (7, 6), (7, 7), (7, 8), (8, 7), (8, 8)], (8, 7): [(0, 7), (8, 0), (1, 7), (8, 1), (2, 7), (8, 2), (3, 7), (8, 3), (4, 7), (8, 4), (5, 7), (8, 5), (6, 7), (8, 6), (7, 7), (8, 8), (6, 6), (6, 7), (6, 8), (7, 6), (7, 7), (7, 8), (8, 6), (8, 8)], (8, 8): [(0, 8), (8, 0), (1, 8), (8, 1), (2, 8), (8, 2), (3, 8), (8, 3), (4, 8), (8, 4), (5, 8), (8, 5), (6, 8), (8, 6), (7, 8), (8, 7), (6, 6), (6, 7), (6, 8), (7, 6), (7, 7), (7, 8), (8, 6), (8, 7)]>

    Find the solution to the above Sudaku Problem

    Output :

    5 3 4 | 6 7 8 | 1 9 2 
    6 7 2 | 1 9 5 | 3 4 8 
    1 9 8 | 3 4 2 | 5 6 7 
    - - - - - - - - - - - 
    8 5 9 | 7 6 1 | 4 2 3 
    4 2 6 | 8 5 3 | 9 7 1 
    7 1 3 | 9 2 4 | 8 5 6 
    - - - - - - - - - - - 
    9 6 1 | 5 3 7 | 2 8 4 
    2 8 7 | 4 1 9 | 6 3 5 
    3 4 5 | 2 8 6 | 7 1 9 

    Full Code :

    Output :

    5 3 0 | 0 7 0 | 0 0 0 
    6 0 0 | 1 9 5 | 0 0 0 
    0 9 8 | 0 0 0 | 0 6 0 
    - - - - - - - - - - - 
    8 0 0 | 0 6 0 | 0 0 3 
    4 0 0 | 8 0 3 | 0 0 1 
    7 0 0 | 0 2 0 | 0 0 6 
    - - - - - - - - - - - 
    0 6 0 | 0 0 0 | 2 8 0 
    0 0 0 | 4 1 9 | 0 0 5 
    0 0 0 | 0 8 0 | 0 0 0 
    ******* Solution *******
    5 3 4 | 6 7 8 | 1 9 2 
    6 7 2 | 1 9 5 | 3 4 8 
    1 9 8 | 3 4 2 | 5 6 7 
    - - - - - - - - - - - 
    8 5 9 | 7 6 1 | 4 2 3 
    4 2 6 | 8 5 3 | 9 7 1 
    7 1 3 | 9 2 4 | 8 5 6 
    - - - - - - - - - - - 
    9 6 1 | 5 3 7 | 2 8 4 
    2 8 7 | 4 1 9 | 6 3 5 
    3 4 5 | 2 8 6 | 7 1 9 

    Real-world Constraint Satisfaction Problems (CSP):

    • Scheduling: A fundamental CSP problem is how to efficiently and effectively schedule resources like personnel, equipment, and facilities. The constraints in this domain specify the availability and capacity of each resource, whereas the variables indicate the time slots or resources.
    • Vehicle routing: Another example of a CSP problem is the issue of minimizing travel time or distance by optimizing a fleet of vehicles’ routes. In this domain, the constraints specify each vehicle’s capacity, delivery locations, and time windows, while the variables indicate the routes taken by the vehicles.
    • Assignment: Another typical CSP issue is how to optimally assign assignments or jobs to humans or machines. In this field, the variables stand in for the tasks, while the constraints specify the knowledge, capacity, and workload of each person or machine.
    • Sudoku: The well-known puzzle game Sudoku can be modeled as a CSP problem, where the variables stand in for the grid’s cells and the constraints specify the game’s rules, such as prohibiting the repetition of the same number in a row, column, or area.
    • Constraint-based image segmentation: The segmentation of an image into areas with various qualities (such as color, texture, or shape) can be treated as a CSP issue in computer vision, where the variables represent the regions and the constraints specify how similar or unlike neighboring regions are to one another.

    Constraint Satisfaction Problems (CSP) benefits:

    • conventional representation patterns
    • generic successor and goal functions
    • Standard heuristics (no domain-specific expertise).