Python Constraint Satisfaction Problem (CSP) Solver

This challenge requires you to build a basic constraint solver in Python. Constraint solvers are powerful tools used to find solutions to problems where a set of variables must satisfy a given set of conditions (constraints). This is fundamental to many areas like scheduling, resource allocation, and artificial intelligence.

Problem Description

You need to implement a generic constraint satisfaction problem (CSP) solver. The solver should be able to take a CSP definition and find one valid assignment of values to variables that satisfies all the given constraints.

Key Requirements:

1. Represent a CSP: You should define a way to represent a CSP, including:

   • Variables: A set of identifiers for the variables.
   • Domains: For each variable, a set of possible values it can take.
   • Constraints: A mechanism to define relationships between variables. A constraint is a function that takes an assignment (a dictionary mapping variables to values) and returns True if the assignment satisfies the constraint, and False otherwise.

2. Backtracking Search Algorithm: Implement a backtracking search algorithm to find a solution. The algorithm should:

   • Select an unassigned variable.
   • Try assigning a value from its domain to the variable.
   • Check if the assignment is consistent with all existing constraints involving assigned variables.
   • If consistent, recursively call itself to assign the next variable.
   • If inconsistent, backtrack and try the next value for the current variable.
   • If all values for the current variable have been tried and no solution is found, backtrack to the previous variable.

3. Return a Solution: The solver should return a dictionary representing a valid assignment of values to all variables if one is found. If no solution exists, it should return None.

Expected Behavior:

The solver should be able to handle different CSPs by being flexible in how variables, domains, and constraints are defined and passed to the solver function.

Edge Cases:

• No Solution: The solver should correctly identify when no assignment can satisfy all constraints.
• Empty CSP: A CSP with no variables or constraints (though typically not a realistic scenario, consider how your code would behave).
• Single Variable CSP: A CSP with only one variable.

Examples

Example 1: Map Coloring

This is a classic CSP. Given a map, assign a color to each region such that no two adjacent regions have the same color.

Input CSP Definition (Conceptual):

• Variables: WA, NT, SA, Q, NSW, V, T (Australian states/territories)
• Domains: {'red', 'green', 'blue'} for all variables.
• Constraints:
  • WA != NT
  • WA != SA
  • NT != SA
  • NT != Q
  • SA != Q
  • SA != NSW
  • SA != V
  • Q != NSW
  • NSW != V
  • (Implicitly, all variables are distinct from each other unless an explicit constraint is given that allows equality. For simplicity in this example, we'll only state explicit inequalities. Your solver should handle a general constraint function.)

Conceptual Input to Solver Function:

variables = ['WA', 'NT', 'SA', 'Q', 'NSW', 'V', 'T']
domains = {var: ['red', 'green', 'blue'] for var in variables}

def get_map_coloring_constraints(variables):
    neighbors = {
        'WA': ['NT', 'SA'],
        'NT': ['WA', 'SA', 'Q'],
        'SA': ['WA', 'NT', 'Q', 'NSW', 'V'],
        'Q': ['NT', 'SA', 'NSW'],
        'NSW': ['Q', 'SA', 'V'],
        'V': ['SA', 'NSW'],
        'T': []
    }
    constraints = []
    for var1 in variables:
        for var2 in neighbors[var1]:
            if var1 < var2: # Avoid duplicate constraints
                constraints.append(lambda assignment, v1=var1, v2=var2: assignment.get(v1) != assignment.get(v2))
    return constraints

# Then call your solver:
# solution = solve_csp(variables, domains, get_map_coloring_constraints(variables))

Potential Output:

{'WA': 'red', 'NT': 'green', 'SA': 'blue', 'Q': 'red', 'NSW': 'green', 'V': 'red', 'T': 'red'}

Explanation: This output is one possible valid coloring. For example, WA is 'red', and its neighbors NT and SA are 'green' and 'blue' respectively, satisfying their constraints. T has no neighbors, so its color can be anything.

Example 2: Simple Sudoku (Simplified)

Consider a tiny 2x2 grid where each row and each column must contain the numbers 1 and 2, and no number can be repeated within a row or column.

Input CSP Definition (Conceptual):

• Variables: (0,0), (0,1), (1,0), (1,1) representing grid cells.
• Domains: {1, 2} for all variables.
• Constraints:
  • cell(0,0) != cell(0,1)
  • cell(1,0) != cell(1,1)
  • cell(0,0) != cell(1,0)
  • cell(0,1) != cell(1,1)

Conceptual Input to Solver Function:

variables = [(r, c) for r in range(2) for c in range(2)]
domains = {var: [1, 2] for var in variables}

def get_2x2_sudoku_constraints():
    constraints = []
    # Row constraints
    constraints.append(lambda assignment: assignment.get((0, 0)) != assignment.get((0, 1)))
    constraints.append(lambda assignment: assignment.get((1, 0)) != assignment.get((1, 1)))
    # Column constraints
    constraints.append(lambda assignment: assignment.get((0, 0)) != assignment.get((1, 0)))
    constraints.append(lambda assignment: assignment.get((0, 1)) != assignment.get((1, 1)))
    return constraints

# Then call your solver:
# solution = solve_csp(variables, domains, get_2x2_sudoku_constraints())

Potential Output:

{(0, 0): 1, (0, 1): 2, (1, 0): 2, (1, 1): 1}

Explanation: This assignment satisfies all row and column constraints. (0,0) is 1, (0,1) is 2 (row 0 is good). (1,0) is 2, (1,1) is 1 (row 1 is good). (0,0) is 1, (1,0) is 2 (column 0 is good). (0,1) is 2, (1,1) is 1 (column 1 is good).

Example 3: No Solution Scenario

Consider the same 2x2 grid, but the domain is only {1}.

Input CSP Definition (Conceptual):

• Variables: (0,0), (0,1), (1,0), (1,1)
• Domains: {1} for all variables.
• Constraints: Same as Example 2 (e.g., cell(0,0) != cell(0,1))

Conceptual Input to Solver Function:

variables = [(r, c) for r in range(2) for c in range(2)]
domains = {var: [1] for var in variables} # Only one possible value

# Use the same constraints as Example 2
# solution = solve_csp(variables, domains, get_2x2_sudoku_constraints())

Output:

None

Explanation: Since all variables can only be 1, it's impossible to satisfy the constraint cell(0,0) != cell(0,1), as both would have to be 1. The solver correctly returns None.

Constraints

• The number of variables in a CSP will be between 1 and 15.
• The size of each variable's domain will be between 1 and 10.
• The total number of constraints will be between 0 and 50.
• Your solver function should have a time complexity that, in the worst case, is exponential in the number of variables, but it should aim to be efficient in practice for typical CSPs.
• The input variables will be an iterable of variable identifiers (strings, numbers, or tuples).
• The input domains will be a dictionary mapping variable identifiers to lists of possible values.
• The input constraints will be a list of constraint functions. Each function takes a partial assignment (a dictionary) and returns True if the assignment is valid with respect to that constraint, False otherwise.

Notes

• You will need to implement the core backtracking search logic.
• Consider how to select the next variable to assign. A simple approach is to pick the first unassigned variable. More advanced heuristics (like Minimum Remaining Values or Degree Heuristic) are not required for this challenge but can significantly improve performance.
• When checking constraints, remember that a constraint function might be called with a partial assignment. It should only return False if the constraint is definitively violated by the partial assignment. If the constraint could still be satisfied with future assignments, it should conceptually return True or not raise an error. A common pattern is to only check variables involved in the constraint that are already assigned.
• The problem asks for one solution. As soon as a valid assignment is found, you can return it.
• This is a foundational challenge. You're building the engine. Focus on the correctness of the backtracking search and constraint checking.