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 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 V1, V2, V3 ……………..Vn.
- Non-empty domain for every single variable D1, D2, D3 …………..Dn.
- The finite set of constraints C1, C2 …….…, Cm.
- where each constraint Ci restricts the possible values for variables,
- e.g., V1 ≠ V2
- Each constraint Ci is a pair <scope, relation>
- Example: <(V1, V2), V1 not equal to V2>
- Scope = set of variables that participate in constraint.
- Relation = list of valid variable value combinations.
- There might be a clear list of permitted combinations. Perhaps a relation that is abstract and that allows for membership testing and listing.
- where each constraint Ci restricts the possible values for variables,
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
Python3
class CSP: def __init__(self, variables, Domains,constraints): self.variables = variables self.domains = Domains self.constraints = constraints self.solution = None def solve(self): assignment = {} self.solution = self.backtrack(assignment) return self.solution def backtrack(self, assignment): if len(assignment) == len(self.variables): return assignment var = self.select_unassigned_variable(assignment) for value in self.order_domain_values(var, assignment): if self.is_consistent(var, value, assignment): assignment[var] = value result = self.backtrack(assignment) if result is not None: return result del assignment[var] return None def select_unassigned_variable(self, assignment): unassigned_vars = [var for var in self.variables if var not in assignment] return min(unassigned_vars, key=lambda var: len(self.domains[var])) def order_domain_values(self, var, assignment): return self.domains[var] def is_consistent(self, var, value, assignment): for constraint_var in self.constraints[var]: if constraint_var in assignment and assignment[constraint_var] == value: return False return True |
Define the Problem
Here we are solving Sudoku Puzzle with Constraint Satisfaction Problems algorithms
Python3
puzzle = [[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] ] def print_sudoku(puzzle): for i in range(9): if i % 3 == 0 and i != 0: print("- - - - - - - - - - - ") for j in range(9): if j % 3 == 0 and j != 0: print(" | ", end="") print(puzzle[i][j], end=" ") print() print_sudoku(puzzle) |
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
Python3
variables = [(i, j) for i in range(9) for j in range(9)] print(variables) |
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
Python3
Domains = {var: set(range(1, 10)) if puzzle[var[0]][var[1]] == 0 else {puzzle[var[0]][var[1]]} for var in variables} print(Domains) |
Output:
{(0, 0): {5},
(0, 1): {3},
(0, 2): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(0, 3): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(0, 4): {7},
(0, 5): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(0, 6): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(0, 7): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(0, 8): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(1, 0): {6},
(1, 1): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(1, 2): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(1, 3): {1},
(1, 4): {9},
(1, 5): {5},
(1, 6): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(1, 7): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(1, 8): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(2, 0): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(2, 1): {9},
(2, 2): {8},
(2, 3): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(2, 4): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(2, 5): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(2, 6): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(2, 7): {6},
(2, 8): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(3, 0): {8},
(3, 1): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(3, 2): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(3, 3): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(3, 4): {6},
(3, 5): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(3, 6): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(3, 7): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(3, 8): {3},
(4, 0): {4},
(4, 1): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(4, 2): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(4, 3): {8},
(4, 4): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(4, 5): {3},
(4, 6): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(4, 7): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(4, 8): {1},
(5, 0): {7},
(5, 1): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(5, 2): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(5, 3): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(5, 4): {2},
(5, 5): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(5, 6): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(5, 7): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(5, 8): {6},
(6, 0): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(6, 1): {6},
(6, 2): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(6, 3): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(6, 4): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(6, 5): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(6, 6): {2},
(6, 7): {8},
(6, 8): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(7, 0): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(7, 1): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(7, 2): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(7, 3): {4},
(7, 4): {1},
(7, 5): {9},
(7, 6): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(7, 7): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(7, 8): {5},
(8, 0): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(8, 1): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(8, 2): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(8, 3): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(8, 4): {8},
(8, 5): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(8, 6): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(8, 7): {1, 2, 3, 4, 5, 6, 7, 8, 9},
(8, 8): {1, 2, 3, 4, 5, 6, 7, 8, 9}}
Define the Constraint for Constraint Satisfaction Problem
Python3
def add_constraint(var): constraints[var] = [] for i in range(9): if i != var[0]: constraints[var].append((i, var[1])) if i != var[1]: constraints[var].append((var[0], i)) sub_i, sub_j = var[0] // 3, var[1] // 3 for i in range(sub_i * 3, (sub_i + 1) * 3): for j in range(sub_j * 3, (sub_j + 1) * 3): if (i, j) != var: constraints[var].append((i, j)) constraints = {} for i in range(9): for j in range(9): add_constraint((i, j)) print(constraints) |
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
Python3
csp = CSP(variables, Domains, constraints) sol = csp.solve() solution = [[0 for i in range(9)] for i in range(9)] for i,j in sol: solution[i][j]=sol[i,j] print_sudoku(solution) |
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 :
Python3
puzzle = [[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] ] def print_sudoku(puzzle): for i in range(9): if i % 3 == 0 and i != 0: print("- - - - - - - - - - - ") for j in range(9): if j % 3 == 0 and j != 0: print(" | ", end="") print(puzzle[i][j], end=" ") print() print_sudoku(puzzle) class CSP: def __init__(self, variables, Domains,constraints): self.variables = variables self.domains = Domains self.constraints = constraints self.solution = None def solve(self): assignment = {} self.solution = self.backtrack(assignment) return self.solution def backtrack(self, assignment): if len(assignment) == len(self.variables): return assignment var = self.select_unassigned_variable(assignment) for value in self.order_domain_values(var, assignment): if self.is_consistent(var, value, assignment): assignment[var] = value result = self.backtrack(assignment) if result is not None: return result del assignment[var] return None def select_unassigned_variable(self, assignment): unassigned_vars = [var for var in self.variables if var not in assignment] return min(unassigned_vars, key=lambda var: len(self.domains[var])) def order_domain_values(self, var, assignment): return self.domains[var] def is_consistent(self, var, value, assignment): for constraint_var in self.constraints[var]: if constraint_var in assignment and assignment[constraint_var] == value: return False return True # Variables variables = [(i, j) for i in range(9) for j in range(9)] # Domains Domains = {var: set(range(1, 10)) if puzzle[var[0]][var[1]] == 0 else {puzzle[var[0]][var[1]]} for var in variables} # Add contraint def add_constraint(var): constraints[var] = [] for i in range(9): if i != var[0]: constraints[var].append((i, var[1])) if i != var[1]: constraints[var].append((var[0], i)) sub_i, sub_j = var[0] // 3, var[1] // 3 for i in range(sub_i * 3, (sub_i + 1) * 3): for j in range(sub_j * 3, (sub_j + 1) * 3): if (i, j) != var: constraints[var].append((i, j)) # constraints constraints = {} for i in range(9): for j in range(9): add_constraint((i, j)) # Solution print('*'*7,'Solution','*'*7) csp = CSP(variables, Domains, constraints) sol = csp.solve() solution = [[0 for i in range(9)] for i in range(9)] for i,j in sol: solution[i][j]=sol[i,j] print_sudoku(solution) |
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).
