Introduction to Constraint Satisfaction

🎓 Introduction to Constraint Satisfaction

Welcome! This is the first in a series of teaching materials designed to introduce you to the world of Constraint Satisfaction and Optimization using the Qaekwy library.

Before we dive into code, it’s important to understand the theory and language that underpin every problem Qaekwy solves. This will give you the right mental model for building your own constraint-based applications.

🌍 Why Learn About CSPs?

Constraint Satisfaction Problems (CSPs) appear everywhere:

  • Scheduling: assigning classes to timeslots, exams to rooms, or employees to shifts.
  • Planning: arranging tasks in manufacturing, logistics, or project management.
  • Configuration: deciding which options of a product can be combined (e.g., car features, software dependencies).
  • Artificial Intelligence: powering puzzles, games, and reasoning systems.

Whenever you are “fitting together pieces under rules,” you are essentially solving a CSP.

🔑 What is a CSP?

At its core, a Constraint Satisfaction Problem is defined by three components:

  1. Variables – the unknowns in the problem. Each represents something we want to decide (e.g., the color of a country, the time of a class, the route of a truck).
  2. Domains – the set of possible values each variable can take. A variable representing a traffic light might have the domain {red, yellow, green}.
  3. Constraints – the rules that restrict how variables can be assigned. Constraints ensure the solution is valid (e.g., “adjacent countries cannot share the same color”).

The goal of a CSP solver is to assign a value to every variable from its domain such that all constraints are satisfied.

🎨 A Classic Example: Map Coloring

Let’s bring this to life with the map coloring problem.

Imagine you have three countries: A, B, and C. You want to assign each a color so that neighboring countries do not share the same color.

  • Variables: Color(A), Color(B), Color(C)

  • Domains: {Red, Green, Blue} for each country

  • Constraints:

    1. Color(A) ≠ Color(B)
    2. Color(B) ≠ Color(C)

That’s it! Now, let’s reason about possible assignments:

  1. Suppose Color(A) = Red.

    • Then Color(B) must be either Green or Blue.
    • If Color(B) = Green, then Color(C) can be Red or Blue.
    • If Color(B) = Blue, then Color(C) can be Red or Green.

From this reasoning, we already see multiple valid solutions:

  • A = Red, B = Green, C = Red
  • A = Red, B = Green, C = Blue
  • A = Red, B = Blue, C = Red
  • A = Red, B = Blue, C = Green

And that’s just starting from A = Red. With symmetry, even more solutions appear. The key is not to find just a solution, but to know that the solver can explore the entire search space efficiently.

🧠 How Do Solvers Approach CSPs?

While humans reason through such examples informally, solvers like Qaekwy follow systematic methods:

  • Backtracking Search: try assignments, roll back when constraints are violated.
  • Constraint Propagation: deduce restrictions before trying values, pruning the search space early.
  • Heuristics: choose which variable or value to try first to speed up solving.

These ideas are what make CSP solvers practical for problems with thousands or millions of possible assignments.

🛠️ How Qaekwy Thinks About CSPs

In Qaekwy, solving a CSP means building a model that encodes the problem. You do this by:

  1. Declaring variables – tell Qaekwy what decisions need to be made.
  2. Defining domains – restrict what values each variable can take.
  3. Adding constraints – write down the logical rules of your problem.

Qaekwy then takes this model and applies its solver engine to find one or more assignments that satisfy all constraints.

Think of it this way: you describe the “what,” Qaekwy handles the “how.”

📖 Glossary (Keep Handy)

  • Variable: An unknown to be decided.
  • Domain: The set of possible values for a variable.
  • Constraint: A rule that restricts assignments.
  • Solution: A complete assignment of values to variables that satisfies all constraints.
  • Model: The structured description of your problem (variables + domains + constraints).
  • Solver: The algorithm that searches for solutions to the model.
  • Search Space: The set of all possible assignments of values to variables.
  • Backtracking: A method of exploring the search space by trying assignments and undoing them when they lead to dead ends.
  • Constraint Propagation: Techniques to reduce domains by enforcing constraints before search.
  • Heuristic: A strategy to guide the search process for efficiency.