Constraint Satisfaction Problems Lecture Notes

Transitioning from Graph Search to Constraint Satisfaction Problems

Previous study focused on informed and uninformed search strategies, where the primary objective is to find a set of actions (a path) from an initial state to a goal. Constraint Satisfaction Problems (CSPs) represent a different class of algorithms where the focus shifts from the sequence of moves to the final state itself.

Atomic versus Factored Representations

Understanding the difference between atomic and factored representations is essential for identifying which algorithm to apply to a specific problem.

Atomic Representation

In an atomic representation, the internal structure of a state is not exposed; the system treats each state as a single, indivisible entity or "node." An example of this is the Rubik's Cube:

• Initial State: A random or scrambled configuration of the cube.

• Goal State: A solved cube where all faces have a uniform color (e.g., right side all red, left side all green, top side all white).

• Actions: Rotating or moving the sides of the cube.

• Solution: A set of actions (moves) that leads from the initial state to the goal state. We know the sequence of actions is a solution if, upon following it, the goal state is achieved.

Factored Representation

In a factored representation, a state is defined by a set of variables, each represented by a value. This allows for a much richer internal structure. An example is the Australian Map Coloring Problem:

• Task: Color the states of an Australian map using three colors—Red, Blue, and Green—in such a way that no two adjacent states share the same color.

• Initial State: A map where no colors have been assigned to any states.

• Goal State: A fully colored map where every assigned color follows the adjacency rules. Unlike a Rubik's Cube, the final visual solution is not immediately obvious; it is determined by rules.

• Actions: Assigning a specific color value to a state.

• Solution: The state itself (the final assignment of variables) rather than the sequence of assignment actions. The order in which colors are assigned does not change the validity of the final solution.

Formal Definition of a Constraint Satisfaction Problem (CSP)

A CSP is defined by three main components:

1. Variables ($X_i$): A set of elements that need values.

2. Domain ($D$): A set of possible values allowed for each variable. Note that for any specific variable ($X_i$), there can be a unique domain ($D_i$).

3. Constraints ($C$): A set of rules specifying which combinations of values are allowed.

An assignment consists of choosing values for some or all variables from their respective domains. A solution is an assignment where every variable is assigned a value in a way that none of the constraints are violated (all constraints are satisfied).

Case Study: Australian Map Coloring

To formalize this problem as a CSP:

• Variables: The states of Australia (Western Australia, Northern Territory, South Australia, Queensland, New South Wales, Victoria, and Tasmania).

• Domain: $\{\text{Red, Green, Blue}\}$.

• Constraints: Two adjacent states cannot have the same color. For example, $\text{South Australia} \neq \text{Western Australia}$ and $\text{South Australia} \neq \text{Northern Territory}$.

Real-World Applications of CSPs

CSPs are widely utilized in industry and logistics, often overlapping with optimization problems (where the goal is to maximize or minimize a specific value):

• Assignment Problems: Dealing with staff schedules (e.g., ensuring a lecturer is not assigned to two rooms at the same time).

• Timetabling: University scheduling involving courses and available classrooms.

• Hardware Configuration: Arranging components on a circuit to minimize space while maintaining functional distance requirements.

• Transport Scheduling: Managing fleets and arrival/departure times.

• Factory Scheduling: Sequencing tasks like casting, milling, drilling, and bolting.

• Gate Assignment at Airports: Assigning planes to gates to minimize the distance passengers must travel for transfers.

Detailed Example: Factory Scheduling

Imagine a robot scheduling manufacturing activities: Casting ($C$), Milling ($M$), Drilling ($D$), and Bolting ($B$).

• Variables: The starting time for each activity.

• Domain: Hours in a day ($1, 2, 3, 4, 5, \dots$).

• Example Constraints:

  • The milling process must start before or at the same time as bolting.

  • Bolting must start before 3:00 PM.

  • Bolting must start before casting.

  • Formally: $(T_M \leq T_B) \land (T_B < 3) \land (T_B < T_C)$.

Classification of Constraints

Constraints can be categorized based on the number of variables involved:

• Unary Constraints: Involve only a single variable (e.g., "Western Australia cannot be Red").

• Binary Constraints: Involve two variables (e.g., "South Australia cannot be the same color as Western Australia"). These can be represented as arcs in a constraint graph.

• Higher-Order Constraints: Involve three or more variables (often found in complex scheduling or logic puzzles).

• Inequality Constraints: Often involve continuous variables (e.g., $X < Y$).

• Soft Constraints (Preferences): These rank different solutions that all satisfy the primary "hard" constraints. For instance, if a lecture could be held at 9:00 AM, 11:00 AM, or 1:00 PM, a soft constraint might prioritize the 1:00 PM slot based on student preference.

Cryptarithmetic Puzzles

Cryptarithmetic is a classic CSP where letters represent unique digits ($0$ to $9$). A famous example is the summation: $\text{SEND} + \text{MORE} = \text{MONEY}$

Problem breakdown:

• Variables: The unique letters: $\text{S, E, N, D, M, O, R, Y}$.

• Domain: Digits $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$.

• Constraints:

  • Every letter must be a unique digit (Alldiff constraint).

  • The first letter of a word cannot be zero ($M \neq 0$ and $S \neq 0$).

  • The summation must be mathematically valid (e.g., $\text{D} + \text{E} = \text{Y}$ or $\text{D} + \text{E} = 10 + \text{Y}$ if there is a carry).

In this specific puzzle, there is only one unique solution. However, there are approximately $10^8$ possible combinations to check if using a blind search. This makes random assignment highly inefficient.

Solving Strategies: Backtracking Search

Generate and Test

This simple algorithm randomly generates a solution and tests if it satisfies the constraints. It is computationally expensive and generally considered infeasible for large or complex problems because the probability of generating a valid solution by chance is infinitesimally small.

Backtracking Algorithm

Backtracking is a more sophisticated approach based on Depth First Search (DFS). It builds a solution incrementally:

1. Initial State: No variables assigned.

2. Action: Pick an unassigned variable and assign it a value from its domain.

3. Consistency Check: Immediately check if the assignment violates any constraints.

4. Pruning: If a violation is found, the algorithm stops exploring that branch, goes back (backtracks), and tries a different value/neighbor.

5. Successor Function: Generates neighbors based on the number of available values. For the Australian map, each state node would have three potential neighbors (Red, Green, Blue).

Logic and Structure of Backtracking

• Recursion: The function calls itself repeatedly, passing down the current assignments and the remaining variables.

• Depth of Search: Unlike standard DFS on an infinite graph, the maximum depth of a CSP backtracking tree is known; it corresponds exactly to the number of variables (e.g., 7 for Australia).

• Constraint Graph: We can represent a CSP as a graph where variables are nodes and binary constraints are arcs. For higher-order constraints, we can introduce specialized nodes representing logical operations (AND/OR) to connect variables.

Questions and Discussion

Q: What happens if you exhaust all legal values for a variable and the successor function fails? A: If all possible values for a variable have been tried and every single one violates a constraint, then no solution exists for that specific branch. If this happens at the top level of the search tree after exploring all options, it means the entire problem has no solution that satisfies every hard constraint.

Q: How does this relate to optimization? A: If a problem has no perfect solution, it can be transitioned into a classical optimization problem. Instead of asking "can all constraints be satisfied?" we ask "what assignment satisfies the maximum number of constraints?" This can be solved using local search algorithms.

Q: Does backtracking repeat work? A: Yes, one issue with basic backtracking is that it can be "blind" to symmetry. For example, if you swap the colors red and green, you might repeat an identical search tree that was already proven to fail. Future lectures will cover methods like local search to improve this efficiency in practice.**