Constraint Satisfaction Problem AI

Constraint Satisfaction Problem AI

2023, Feb 05    

Introduction

Constraint Satisfaction Problems (CSPs) form the backbone of many AI applications, from scheduling systems to puzzle solvers. As part of CISC 352 at Queen’s University, I developed a comprehensive CSP solver for Cagey—a challenging logic puzzle that combines the structural complexity of Sudoku with dynamic cage constraints similar to KenKen.

This project provided an opportunity to explore the theoretical foundations of CSPs while tackling the practical challenges of implementation. The solver incorporates multiple constraint propagation techniques, intelligent variable selection heuristics, and flexible constraint modeling approaches. Through this implementation, I gained hands-on experience with the delicate balance between computational efficiency and solution completeness that defines effective CSP solvers.

Understanding the Cagey Puzzle

Before diving into the technical implementation, it’s essential to understand what makes Cagey such an interesting CSP. Cagey is a logic-based puzzle game that shares DNA with both Sudoku and KenKen, but introduces unique challenges that make it particularly well-suited for CSP techniques.

The game is played on an nxn grid with three fundamental constraints:

  1. Uniqueness Constraints: Each row and column must contain unique numbers from 1 to n, similar to Sudoku.

  2. Cage Constraints: The grid is divided into “cages”—groups of cells with a specified target value and operation. The numbers within each cage must combine using the specified operation (addition +, subtraction -, multiplication *, division /, or unknown ?) to equal the target value.

  3. Flexibility Within Cages: Numbers in each cage can be arranged in any order to achieve the target value, providing multiple valid solutions for individual cages.

Consider a 3×3 grid where a cage might require three cells to sum to 6 (6+), while a single-cell cage might simply need to equal 3 (3?). The real challenge emerges when the operation is unknown (?), requiring the solver to determine both the operation and valid number combinations.

What makes Cagey particularly challenging is how it layered the familiar row-column uniqueness constraints with the dynamic, variable-arity cage constraints. This combination creates a rich constraint network that benefits from sophisticated propagation and search strategies.

Architecture and Design Philosophy

The implementation consists of several interconnected components that work together to solve increasingly complex puzzles:

Core Components

Constraint Propagation Engine: Two complementary propagators—Forward Checking (FC) and Generalized Arc Consistency (GAC)—form the backbone of the search space reduction strategy, They integrate with a backtracking search framework.

Intelligent Variable Selection: Two heuristic strategies guide the search process: Minimum Remaining Values (MRV) for identifying the most constrained variables, and Degree Heuristic (DH) for tie-breaking based on constraint connectivity.

Flexible Constraint Modeling: Multiple modeling approaches handle different aspects of the Cagey puzzle, from simple binary not-equal constraints to complex n-ary cage constraints that must dynamically evaluate mathematical operations.

Constraint Modeling

Effective constraint modeling is at the heart of solving Cagey puzzles, as it directly impacts the solver’s ability to efficiently navigate the search space. The Cagey solver employs three distinct modeling approaches, each tailored to balance expressiveness, memory usage, and computational efficiency based on the problem’s unique requirements. Together, these models form a cohesive strategy for tackling Cagey puzzles, enabling the solver to efficiently navigate the intricate constraint network while maintaining the flexibility needed to handle diverse cage configurations.

Binary Constraints: Simplicity and Scalability

The Cagey puzzle’s row and column uniqueness constraints can be modeled using pairwise binary constraints. The binary_ne_grid(cagey_grid) function decomposes these constraints into simpler relationships, ensuring that each pair of variables within a row or column are not equal.

for row in grid:
    for i in range(n):
        for j in range(i+1, n):
            con = Constraint("Row NE", [row[i], row[j]])
            con.add_satisfying_tuples([(a, b) for a in domain for b in domain if a != b])
            csp.add_constraint(con)

for col in zip(*grid):
    for i in range(n):
        for j in range(i+1, n):
            con = Constraint("Col NE", [col[i], col[j]])
            con.add_satisfying_tuples([(a, b) for a in domain for b in domain if a != b])
            csp.add_constraint(con)

This approach generates a large number of constraints (O(n³) for an n×n grid), but each constraint is computationally lightweight and memory-efficient. Binary constraints are particularly effective for smaller grids or scenarios where memory is limited, as they break down complex relationships into manageable pieces.

N-ary Constraints: Expressive Power for Larger Grids

For larger grids, the solver leverages n-ary constraints to model row and column uniqueness more directly. The nary_ad_grid(cagey_grid) function uses all-different constraints, which encapsulate the uniqueness requirement for an entire row or column in a single constraint.

for row in grid:
    con = Constraint("Row AD", row)
    con.add_satisfying_tuples(list(itertools.permutations(domain)))
    csp.add_constraint(con)

for col in zip(*grid):
    con = Constraint("Col AD", list(col))
    con.add_satisfying_tuples(list(itertools.permutations(domain)))
    csp.add_constraint(con)

This approach reduces the number of constraints (O(n) instead of O(n³)) but requires enumerating all permutations of the domain, leading to significant memory overhead. While computationally expensive, n-ary constraints enable more effective propagation, making them ideal for larger grids where the solver benefits from reduced constraint complexity.

Cage Constraints: Capturing Problem-Specific Complexity

The most challenging aspect of Cagey puzzles lies in modeling the cage constraints, which combine variable-arity operations and dynamic requirements. The cagey_csp_model(cagey_grid) function dynamically generates constraints based on cage specifications, handling both known and unknown operations.

for cage in cages:
    target, cells, op = cage
    scope = [grid[i-1][j-1] for (i,j) in cells]
    con = Constraint("Cage", scope)
    valid_tuples = []
    for t in itertools.product(domain, repeat=len(scope)):
        if is_valid_cage_tuple(t, target, op):
            valid_tuples.append(t)
    con.add_satisfying_tuples(valid_tuples)
    csp.add_constraint(con)

This approach showcases the flexibility required for real-world CSP applications. When the operation is unknown (op == '?'), the solver must test all possible operators, creating a unified constraint that captures the disjunctive nature of the cage requirement. By dynamically generating constraints, the solver adapts to the unique structure of each puzzle, ensuring both accuracy and efficiency.

Constraint Propagation for Reducing Search Space

Constraint propagation is useful because rather than blindly exploring the exponential search space, these techniques systematically eliminate inconsistent values, dramatically reducing the number of possibilities the solver must consider.

Forward Checking

When a variable selection is made (value of a cell or operator for a cage), Forward Checking immediately looks ahead to see what effect this decision has on future choices. It checks if there are any future options that would be rendered invalid by the current decision. If a decision leads to a situation where no valid options remain for some variable, that branch can be eliminated early, avoiding needless exploration of impossible paths. The prop_FC(csp, newVar=None) function implements this look-ahead strategy:

if newVar:
    cons = csp.get_cons_with_var(newVar)
else:
    cons = csp.get_all_cons()

for con in cons:
    if con.get_n_unasgn() == 1:
        V = con.get_unasgn_vars()[0]
        for d in V.cur_domain():
            if not con.check_var_val(V, d):
                V.prune_value(d)
                pruned.append((V, d))
        if V.cur_domain_size() == 0:
            return False, pruned

Forward Checking is so powerful here because when only one variable remains unassigned in a constraint, we can immediately determine which values are still viable. This anticipatory pruning prevents the solver from making assignments that will inevitably lead to dead ends.

Generalized Arc Consistency

The prop_GAC(csp, newVar=None) function ensures that every remaining variable-value pair has explicit support within the constraint network.

if newVar:
    queue = list(csp.get_cons_with_var(newVar))
else:
    queue = list(csp.get_all_cons())

while queue:
    con = queue.pop(0)
    for var in con.get_scope():
        for val in var.cur_domain():
            if not con.check_var_val(var, val):
                var.prune_value(val)
                pruned.append((var, val))
                if var.cur_domain_size() == 0:
                    return False, pruned
                for c in csp.get_cons_with_var(var):
                    if c not in queue:
                        queue.append(c)

GAC exhibits a cascading effect in pruning. When GAC removes a value from a variable’s domain, it re-examines all constraints involving that variable, potentially triggering additional pruning. This creates a propagation cascade that can dramatically reduce the search space, though at the cost of increased computational overhead per propagation step.

The choice between FC and GAC invloves a tradeoff: GAC performs more work upfront but can prevent extensive backtracking later, while FC provides faster individual propagation steps but may require more search iterations.

Guiding the Search With Strategic Variable Selection

Even with effective constraint propagation, the order in which variables are assigned can dramatically impact solver performance. The two heuristics implemented in this project represent complementary approaches to this fundamental challenge.

Minimum Remaining Values

The Minimum Remaining Values (MRV) heuristic selects the variable with the smallest remaining domain. The function ord_mrv(csp) forces the solver to confront the most constrained decisions first.

min_var = None
min_size = float('inf')
for var in csp.get_all_unasgn_vars():
    size = var.cur_domain_size()
    if size < min_size:
        min_size = size
        min_var = var
return min_var

By tackling the most constrained variables early, MRV ensures that any inconsistencies are discovered as quickly as possible, minimizing wasted computational effort on ultimately futile search branches.

Degree Heuristic

When multiple variables tie for the smallest domain size, the Degree Heuristic (DH) provides intelligent tie-breaking. The ord_dh(csp) function selects the variable involved in the most constraints with other unassigned variables.

max_var = None
max_degree = -1
for var in csp.get_all_unasgn_vars():
    degree = 0
    for con in csp.get_cons_with_var(var):
        if any(not v.is_assigned() and v != var for v in con.get_scope()):
            degree += 1
    if degree > max_degree:
        max_degree = degree
        max_var = var
return max_var

The intuition behind DH is that variables with more constraints have greater potential to trigger propagation cascades. By choosing highly connected variables, the solver maximizes the likelihood that each assignment will provide valuable information about other variables’ domains.

Together, MRV and DH create a powerful variable selection strategy that balances immediate constraint pressure with longer-term propagation benefits.

Lessons Learned

The development of the Cagey CSP solver provided invaluable insights into the practical challenges of implementing theoretical algorithms. Several key lessons emerged from this experience:

The Art of Trade-offs: Every design decision in CSP solving involves trade-offs. GAC provides more thorough propagation than Forward Checking but requires more computation per step. N-ary constraints offer greater expressiveness than binary constraints but consume exponentially more memory. The most effective solver configurations often involve careful balancing of these competing concerns based on the specific problem characteristics.

Modeling Matters: Perhaps the most surprising insight was how dramatically different constraint models could affect solver performance. The same logical puzzle could become trivially easy or computationally intensive depending on how constraints were formulated and encoded. This emphasized that successful CSP application requires deep understanding of both the problem domain and the underlying algorithmic machinery.

Dynamic Constraint Generation: The cage constraints, particularly those with unknown operations, highlighted the need for flexible constraint generation mechanisms. Real-world CSP applications often require constraints that cannot be enumerated statically but must be generated dynamically based on problem instance characteristics.

Reflection

This assignment offered a rich introduction to CSPs. Implementing both Forward Checking and GAC deepened my appreciation for constraint propagation’s role in pruning search spaces. The shift from binary to n-ary constraints also illustrated how structural modeling choices affect solver performance. Most importantly, building cage constraints demanded a real synthesis of algorithmic thinking and practical coding.

From variable domain pruning to constraint satisfaction under ambiguity, Cagey was a perfect testbed for building a high-performance, general-purpose CSP engine.

# CSP # Constraint Satisfaction # Python # AI