Map Coloring → Timetable Scheduling

Why Constraint Satisfaction Problems?

Many real-world tasks are “fill in the blanks but obey rules.” Think exam timetables (no instructor in two places at once), meeting room bookings (one meeting per room/time), or coloring maps (adjacent regions get different colors). These are Constraint Satisfaction Problems (CSPs). Instead of searching actions over time, CSPs search assignments to variables while enforcing constraints.

You’ll learn how to model a problem as a CSP, use constraint propagation (AC-3) and smart heuristics (MRV, LCV), and solve both a classic map coloring toy problem and a practical timetable scheduling problem—all in clean, dependency-free Python.

Theory Deep Dive

1. Formal Definition

A CSP is a triple $\langle X, D, C \rangle$ , where:

Variables: $X={X_1,\ldots,X_n}$
Domains: $D={D_1,\ldots,D_n}$ with $X_i \in D_i$
Constraints: $C={C_1,\ldots,C_m}$ , each constraint limits allowed tuples of values for a subset of variables.

A (partial) assignment $A$ maps some variables to values; a solution is a complete assignment satisfying all constraints:
$\forall C_k \in C,; A \text{ satisfies } C_k.$

2. Types of consistency

Node consistency: every value in $D_i$ satisfies unary constraints on $X_i$ .

Arc consistency (binary CSPs): for each pair $(X_i, X_j)$ with constraint $C_{ij} \subseteq D_i \times D_j$ ,
$\forall x \in D_i,; \exists y \in D_j \text{ s.t. } (x,y) \in C_{ij}.$
If no such $y$ exists, remove $x$ from $D_i$ .

3. Propagation: AC-3

Idea: Repeatedly prune values that have no supporting partner across a constraint.
Complexity: $O(ed^3)$ for binary CSPs, where $e$ is number of arcs and $d=\max_i |D_i|$ .

4. Search with heuristics

Backtracking search: try values variable-by-variable; backtrack on conflict. Worst case $O(d^n)$ .

MRV (Minimum Remaining Values): choose variable with smallest current domain (most constrained).

Degree heuristic: tie-breaker—pick variable involved in most constraints with unassigned variables.

LCV (Least Constraining Value): among candidate values, try the one that rules out fewest values in neighbors first.

Forward checking / Maintaining Arc Consistency (MAC): do local propagation after each assignment to fail early.

5. Local Search (optional)

Min-conflicts: start with a random complete assignment; iteratively fix variables in conflict by choosing a value that minimizes conflicts. Great for large, nearly-satisfiable CSPs (e.g., scheduling).

Toy Problem – Map Coloring (Australia)

Problem setup & Dataset Snapshot (Representation)

Goal: Color each region so that no adjacent regions share a color.
Variables: $X = {\text{WA},\text{NT},\text{SA},\text{Q},\text{NSW},\text{V},\text{T}}$
Domains: $D = {\text{Red},\text{Green},\text{Blue}}$ for each variable
Adjacency (binary inequality constraints):

Region	Neighbors
WA	NT, SA
NT	WA, SA, Q
SA	WA, NT, Q, NSW, V
Q	NT, SA, NSW
NSW	SA, Q, V
V	SA, NSW
T	(none)

Constraint for any neighboring pair $(X_i, X_j)$ : $X_i \neq X_j$ .

Step 1: CSP scaffolding (variables, domains, neighbors, constraints)

Defines a minimal CSP class with variable sets, domain sets, neighbor graph, and a constraint predicate.

# csp_core.py — basic structures
from collections import deque, defaultdict
from copy import deepcopy

class CSP:
    def __init__(self, variables, domains, neighbors, constraint):
        self.variables = variables                    # list[str]
        self.domains = {v: list(domains[v]) for v in variables}
        self.neighbors = neighbors                    # dict[var] -> list[neighbor vars]
        self.constraint = constraint                  # fn(Xi, vi, Xj, vj) -> bool

    def copy(self):
        c = CSP(self.variables, self.domains, self.neighbors, self.constraint)
        c.domains = {v: list(vals) for v, vals in self.domains.items()}
        return c

Step 2: AC-3 algorithm for arc consistency

Prunes unsupported values; re-enqueues affected arcs when pruning occurs.

def AC3(csp):
    queue = deque()
    for Xi in csp.variables:
        for Xj in csp.neighbors[Xi]:
            queue.append((Xi, Xj))

    def revise(Xi, Xj):
        revised = False
        to_remove = []
        for x in csp.domains[Xi]:
            if not any(csp.constraint(Xi, x, Xj, y) for y in csp.domains[Xj]):
                to_remove.append(x)
        if to_remove:
            for x in to_remove:
                csp.domains[Xi].remove(x)
            revised = True
        return revised

    while queue:
        Xi, Xj = queue.popleft()
        if revise(Xi, Xj):
            if not csp.domains[Xi]:
                return False
            for Xk in csp.neighbors[Xi]:
                if Xk != Xj:
                    queue.append((Xk, Xi))
    return True

Step 3: Heuristics: MRV + Degree, and LCV ordering

Chooses the next variable via MRV (then Degree) and orders values via LCV.

def select_unassigned_var(assignment, csp):
    unassigned = [v for v in csp.variables if v not in assignment]
    # MRV
    m = min(len(csp.domains[v]) for v in unassigned)
    candidates = [v for v in unassigned if len(csp.domains[v]) == m]
    if len(candidates) == 1:
        return candidates[0]
    # Degree heuristic tie-breaker
    return max(candidates, key=lambda v: sum(1 for n in csp.neighbors[v] if n not in assignment))

def order_values_lcv(var, csp, assignment):
    def conflicts(value):
        cnt = 0
        for n in csp.neighbors[var]:
            if n not in assignment:
                for y in csp.domains[n]:
                    if not csp.constraint(var, value, n, y):
                        cnt += 1
        return cnt
    return sorted(csp.domains[var], key=conflicts)

4. Forward checking helper

After assigning a value, remove incompatible neighbor values; restore when backtracking.

def forward_check(var, value, csp, assignment, pruned):
    for n in csp.neighbors[var]:
        if n in assignment:
            continue
        for y in list(csp.domains[n]):
            if not csp.constraint(var, value, n, y):
                csp.domains[n].remove(y)
                pruned.append((n, y))
        if not csp.domains[n]:  # domain wipeout
            return False
    return True

def restore_pruned(csp, pruned):
    for (v, x) in pruned:
        if x not in csp.domains[v]:
            csp.domains[v].append(x)

5. Backtracking search (with AC-3 prepass, MRV/LCV, forward checking)

Combines propagation and search to find a satisfying assignment.

def backtrack(assignment, csp):
    if len(assignment) == len(csp.variables):
        return assignment

    var = select_unassigned_var(assignment, csp)
    for value in order_values_lcv(var, csp, assignment):
        # Check local consistency with already-assigned neighbors
        if all(csp.constraint(var, value, n, assignment[n]) for n in csp.neighbors[var] if n in assignment):
            assignment[var] = value
            pruned = []
            if forward_check(var, value, csp, assignment, pruned):
                result = backtrack(assignment, csp)
                if result is not None:
                    return result
            restore_pruned(csp, pruned)
            del assignment[var]
    return None

def solve_csp(csp, use_ac3=True):
    work = csp.copy()
    if use_ac3 and not AC3(work):
        return None
    return backtrack({}, work)

6. Build the Australia map CSP and solve

Encodes “adjacent regions must differ” and prints a valid coloring (one of many).

# Problem instance
variables = ["WA","NT","SA","Q","NSW","V","T"]
colors = ["Red","Green","Blue"]
domains = {v: colors for v in variables}
neighbors = {
    "WA": ["NT","SA"],
    "NT": ["WA","SA","Q"],
    "SA": ["WA","NT","Q","NSW","V"],
    "Q":  ["NT","SA","NSW"],
    "NSW":["SA","Q","V"],
    "V":  ["SA","NSW"],
    "T":  []
}

def not_equal_constraint(Xi, vi, Xj, vj):
    return vi != vj

map_csp = CSP(variables, domains, neighbors, not_equal_constraint)
solution = solve_csp(map_csp, use_ac3=True)
print(solution)

Quick Reference: Full Code

from collections import deque
from copy import deepcopy

class CSP:
    def __init__(self, variables, domains, neighbors, constraint):
        self.variables = variables
        self.domains = {v: list(domains[v]) for v in variables}
        self.neighbors = neighbors
        self.constraint = constraint
    def copy(self):
        c = CSP(self.variables, self.domains, self.neighbors, self.constraint)
        c.domains = {v: list(vals) for v, vals in self.domains.items()}
        return c

def AC3(csp):
    queue = deque((Xi, Xj) for Xi in csp.variables for Xj in csp.neighbors[Xi])
    def revise(Xi, Xj):
        revised = False
        to_remove = []
        for x in csp.domains[Xi]:
            if not any(csp.constraint(Xi, x, Xj, y) for y in csp.domains[Xj]):
                to_remove.append(x)
        for x in to_remove:
            csp.domains[Xi].remove(x)
            revised = True
        return revised
    while queue:
        Xi, Xj = queue.popleft()
        if revise(Xi, Xj):
            if not csp.domains[Xi]:
                return False
            for Xk in csp.neighbors[Xi]:
                if Xk != Xj:
                    queue.append((Xk, Xi))
    return True

def select_unassigned_var(assignment, csp):
    unassigned = [v for v in csp.variables if v not in assignment]
    m = min(len(csp.domains[v]) for v in unassigned)
    candidates = [v for v in unassigned if len(csp.domains[v]) == m]
    if len(candidates) == 1:
        return candidates[0]
    return max(candidates, key=lambda v: sum(1 for n in csp.neighbors[v] if n not in assignment))

def order_values_lcv(var, csp, assignment):
    def conflicts(value):
        cnt = 0
        for n in csp.neighbors[var]:
            if n not in assignment:
                for y in csp.domains[n]:
                    if not csp.constraint(var, value, n, y):
                        cnt += 1
        return cnt
    return sorted(csp.domains[var], key=conflicts)

def forward_check(var, value, csp, assignment, pruned):
    for n in csp.neighbors[var]:
        if n in assignment:
            continue
        for y in list(csp.domains[n]):
            if not csp.constraint(var, value, n, y):
                csp.domains[n].remove(y)
                pruned.append((n, y))
        if not csp.domains[n]:
            return False
    return True

def restore_pruned(csp, pruned):
    for (v, x) in pruned:
        if x not in csp.domains[v]:
            csp.domains[v].append(x)

def backtrack(assignment, csp):
    if len(assignment) == len(csp.variables):
        return assignment
    var = select_unassigned_var(assignment, csp)
    for value in order_values_lcv(var, csp, assignment):
        if all(csp.constraint(var, value, n, assignment[n]) for n in csp.neighbors[var] if n in assignment):
            assignment[var] = value
            pruned = []
            if forward_check(var, value, csp, assignment, pruned):
                result = backtrack(assignment, csp)
                if result is not None:
                    return result
            restore_pruned(csp, pruned)
            del assignment[var]
    return None

def solve_csp(csp, use_ac3=True):
    work = csp.copy()
    if use_ac3 and not AC3(work):
        return None
    return backtrack({}, work)

# Australia map coloring
variables = ["WA","NT","SA","Q","NSW","V","T"]
colors = ["Red","Green","Blue"]
domains = {v: colors for v in variables}
neighbors = {
    "WA": ["NT","SA"], "NT": ["WA","SA","Q"], "SA": ["WA","NT","Q","NSW","V"],
    "Q":  ["NT","SA","NSW"], "NSW":["SA","Q","V"], "V":["SA","NSW"], "T":[]
}
def neq(Xi, vi, Xj, vj): return vi != vj
map_csp = CSP(variables, domains, neighbors, neq)
print(solve_csp(map_csp, use_ac3=True))

Real‑World Application — Timetable Scheduling

Problem Setup

We’ll schedule a small university’s classes. Each course needs a (time slot, room).
Constraints:

No instructor teaches two classes at the same time.
No room hosts two classes at the same time.
Room capacity must be $\ge$ course enrollment.
Some pairs of courses cannot be at the same time (e.g., shared students or policy).

Data snapshot (example):

Timeslots: Mon9, Mon10, Tue9, Tue10
Rooms (capacity): R101(40), R102(30)
Courses (enrollment, instructor):
- CS101(35, ProfA)
- CS102(25, ProfA)
- EE201(30, ProfB)
- MATH210(28, ProfC)
- STAT110(22, ProfC)
Forbidden same-time pairs: {(CS101, EE201)} (share many students)

We’ll let each course’s domain be all feasible (timeslot, room) pairs that meet capacity.

Step 1: Build candidate domains (capacity filtering)

Generates capacity-feasible (time, room) pairs for each course.

timeslots = ["Mon9", "Mon10", "Tue9", "Tue10"]
rooms = {"R101": 40, "R102": 30}

courses = {
    "CS101":  {"enroll": 35, "instr": "ProfA"},
    "CS102":  {"enroll": 25, "instr": "ProfA"},
    "EE201":  {"enroll": 30, "instr": "ProfB"},
    "MATH210":{"enroll": 28, "instr": "ProfC"},
    "STAT110":{"enroll": 22, "instr": "ProfC"},
}

forbidden_same_time = {("CS101", "EE201"), ("EE201","CS101")}

variables = list(courses.keys())

def feasible_pairs(course):
    need = courses[course]["enroll"]
    pairs = []
    for t in timeslots:
        for r, cap in rooms.items():
            if cap >= need:
                pairs.append((t, r))
    return pairs

domains = {c: feasible_pairs(c) for c in courses}

Step 2: Neighbor graph (everyone potentially conflicts with everyone)

Timetabling is dense: most pairs can interact via room/instructor/time constraints.

neighbors = {c: [d for d in variables if d != c] for c in variables}

Step 3: Constraint predicate (room, instructor, forbidden pairs)

Encodes three common hard constraints; capacity was pre-filtered.

def schedule_constraint(Ci, vi, Cj, vj):
    # vi = (time_i, room_i), vj = (time_j, room_j)
    ti, ri = vi
    tj, rj = vj

    # 1) Room uniqueness at same time
    if ti == tj and ri == rj:
        return False

    # 2) Instructor cannot be double-booked
    same_time = (ti == tj)
    if same_time and courses[Ci]["instr"] == courses[Cj]["instr"]:
        return False

    # 3) Forbidden same-time pairs
    if same_time and (Ci, Cj) in forbidden_same_time:
        return False

    return True

Step 4: Build CSP and solve (reuse solver from Section 3)

Produces a conflict-free timetable if one exists.

sched_csp = CSP(variables, domains, neighbors, schedule_constraint)
solution = solve_csp(sched_csp, use_ac3=True)
print(solution)

Step 5: Pretty-print the schedule

Groups courses by timeslot for quick human review.

from collections import defaultdict

def pretty_schedule(assign):
    by_time = defaultdict(list)
    for course, (t, r) in sorted(assign.items()):
        by_time[t].append(f"{course} in {r} ({courses[course]['instr']})")
    for t in sorted(by_time.keys()):
        print(f"{t}:")
        for line in by_time[t]:
            print("  - " + line)

if solution:
    pretty_schedule(solution)
else:
    print("No feasible schedule found.")

Quick Reference: Full Code

from collections import deque, defaultdict

class CSP:
    def __init__(self, variables, domains, neighbors, constraint):
        self.variables = variables
        self.domains = {v: list(domains[v]) for v in variables}
        self.neighbors = neighbors
        self.constraint = constraint
    def copy(self):
        c = CSP(self.variables, self.domains, self.neighbors, self.constraint)
        c.domains = {v: list(vals) for v, vals in self.domains.items()}
        return c

def AC3(csp):
    queue = deque((Xi, Xj) for Xi in csp.variables for Xj in csp.neighbors[Xi])
    def revise(Xi, Xj):
        revised = False
        to_remove = []
        for x in csp.domains[Xi]:
            if not any(csp.constraint(Xi, x, Xj, y) for y in csp.domains[Xj]):
                to_remove.append(x)
        for x in to_remove:
            csp.domains[Xi].remove(x)
            revised = True
        return revised
    while queue:
        Xi, Xj = queue.popleft()
        if revise(Xi, Xj):
            if not csp.domains[Xi]:
                return False
            for Xk in csp.neighbors[Xi]:
                if Xk != Xj:
                    queue.append((Xk, Xi))
    return True

def select_unassigned_var(assignment, csp):
    unassigned = [v for v in csp.variables if v not in assignment]
    m = min(len(csp.domains[v]) for v in unassigned)
    candidates = [v for v in unassigned if len(csp.domains[v]) == m]
    if len(candidates) == 1:
        return candidates[0]
    return max(candidates, key=lambda v: sum(1 for n in csp.neighbors[v] if n not in assignment))

def order_values_lcv(var, csp, assignment):
    def conflicts(value):
        cnt = 0
        for n in csp.neighbors[var]:
            if n not in assignment:
                for y in csp.domains[n]:
                    if not csp.constraint(var, value, n, y):
                        cnt += 1
        return cnt
    return sorted(csp.domains[var], key=conflicts)

def forward_check(var, value, csp, assignment, pruned):
    for n in csp.neighbors[var]:
        if n in assignment:
            continue
        for y in list(csp.domains[n]):
            if not csp.constraint(var, value, n, y):
                csp.domains[n].remove(y)
                pruned.append((n, y))
        if not csp.domains[n]:
            return False
    return True

def restore_pruned(csp, pruned):
    for (v, x) in pruned:
        if x not in csp.domains[v]:
            csp.domains[v].append(x)

def backtrack(assignment, csp):
    if len(assignment) == len(csp.variables):
        return assignment
    var = select_unassigned_var(assignment, csp)
    for value in order_values_lcv(var, csp, assignment):
        if all(csp.constraint(var, value, n, assignment[n]) for n in csp.neighbors[var] if n in assignment):
            assignment[var] = value
            pruned = []
            if forward_check(var, value, csp, assignment, pruned):
                result = backtrack(assignment, csp)
                if result is not None:
                    return result
            restore_pruned(csp, pruned)
            del assignment[var]
    return None

def solve_csp(csp, use_ac3=True):
    work = csp.copy()
    if use_ac3 and not AC3(work):
        return None
    return backtrack({}, work)

# Timetable data
timeslots = ["Mon9", "Mon10", "Tue9", "Tue10"]
rooms = {"R101": 40, "R102": 30}
courses = {
    "CS101":  {"enroll": 35, "instr": "ProfA"},
    "CS102":  {"enroll": 25, "instr": "ProfA"},
    "EE201":  {"enroll": 30, "instr": "ProfB"},
    "MATH210":{"enroll": 28, "instr": "ProfC"},
    "STAT110":{"enroll": 22, "instr": "ProfC"},
}
forbidden_same_time = {("CS101","EE201"), ("EE201","CS101")}
variables = list(courses.keys())

def feasible_pairs(course):
    need = courses[course]["enroll"]
    pairs = []
    for t in timeslots:
        for r, cap in rooms.items():
            if cap >= need:
                pairs.append((t, r))
    return pairs

domains = {c: feasible_pairs(c) for c in courses}
neighbors = {c: [d for d in variables if d != c] for c in variables}

def schedule_constraint(Ci, vi, Cj, vj):
    ti, ri = vi; tj, rj = vj
    if ti == tj and ri == rj:               return False     # room clash
    if ti == tj and courses[Ci]["instr"] == courses[Cj]["instr"]:  return False  # instructor clash
    if ti == tj and (Ci, Cj) in forbidden_same_time:        return False
    return True

sched_csp = CSP(variables, domains, neighbors, schedule_constraint)
solution = solve_csp(sched_csp, use_ac3=True)

from collections import defaultdict
def pretty_schedule(assign):
    by_time = defaultdict(list)
    for course, (t, r) in sorted(assign.items()):
        by_time[t].append(f"{course} in {r} ({courses[course]['instr']})")
    for t in sorted(by_time.keys()):
        print(f"{t}:")
        for line in by_time[t]:
            print("  - " + line)

if solution:
    pretty_schedule(solution)
else:
    print("No feasible schedule found.")

Strengths & Limitations

Strengths

Declarative modeling: You focus on what must be true (constraints), not how to get there.
Powerful pruning: Propagation (AC-3/MAC) + heuristics (MRV/LCV) drastically reduce search.
Reusability: Same solver can serve many domains (maps, timetables, resource allocation).

Limitations

Worst-case exponential: Backtracking still explodes for very hard instances.
Modeling effort: Good performance often needs good variable/domain design and constraints.
Soft constraints/objectives: Pure CSPs are about feasibility; optimization needs extensions (e.g., Weighted CSP, COP).

Final Notes

You learned to: (1) formalize problems as $\langle X,D,C \rangle$ , (2) apply arc consistency for early pruning, (3) use MRV/LCV and forward checking to guide search, and (4) implement end-to-end solvers for map coloring and a practical timetable.

This mindset—state as assignments + constraints—is widely applicable in operations, logistics, and education scheduling.

Next Steps for You:

Scale up & Min-Conflicts: Try a larger timetable (more rooms/slots); compare backtracking vs. min-conflicts local search.

Optimization: Extend to Constraint Optimization Problems (COP): add penalties for late classes or instructor preferences; implement a simple cost function and use best-first search or simulated annealing.

References

[1] S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. Pearson, 2020.
[2] R. Dechter, Constraint Processing. Morgan Kaufmann, 2003.
[3] A. K. Mackworth, “Consistency in networks of relations,” Artificial Intelligence, vol. 8, no. 1, pp. 99–118, 1977.
[4] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
[5] S. Minton, M. D. Johnston, A. B. Philips, and P. Laird, “Minimizing conflicts: a heuristic repair method for constraint-satisfaction and scheduling problems,” Artificial Intelligence, vol. 58, pp. 161–205, 1992.

Constraint Satisfaction Problems (CSP): Solve Complex Choices with Rules

Why Constraint Satisfaction Problems?

Theory Deep Dive

1. Formal Definition

2. Types of consistency

3. Propagation: AC-3

4. Search with heuristics

5. Local Search (optional)

Toy Problem – Map Coloring (Australia)

Problem setup & Dataset Snapshot (Representation)

Step 1: CSP scaffolding (variables, domains, neighbors, constraints)

Step 2: AC-3 algorithm for arc consistency

Step 3: Heuristics: MRV + Degree, and LCV ordering

4. Forward checking helper

5. Backtracking search (with AC-3 prepass, MRV/LCV, forward checking)

6. Build the Australia map CSP and solve

Quick Reference: Full Code

Real‑World Application — Timetable Scheduling

Problem Setup

Step 1: Build candidate domains (capacity filtering)

Step 2: Neighbor graph (everyone potentially conflicts with everyone)

Step 3: Constraint predicate (room, instructor, forbidden pairs)

Step 4: Build CSP and solve (reuse solver from Section 3)

Step 5: Pretty-print the schedule

Quick Reference: Full Code

Strengths & Limitations

Strengths

Limitations

Final Notes

References

Leave a comment Cancel reply

Constraint Satisfaction Problems (CSP): Solve Complex Choices with Rules

Why Constraint Satisfaction Problems?

Theory Deep Dive

1. Formal Definition

2. Types of consistency

3. Propagation: AC-3

4. Search with heuristics

5. Local Search (optional)

Toy Problem – Map Coloring (Australia)

Problem setup & Dataset Snapshot (Representation)

Step 1: CSP scaffolding (variables, domains, neighbors, constraints)

Step 2: AC-3 algorithm for arc consistency

Step 3: Heuristics: MRV + Degree, and LCV ordering

4. Forward checking helper

5. Backtracking search (with AC-3 prepass, MRV/LCV, forward checking)

6. Build the Australia map CSP and solve

Quick Reference: Full Code

Real‑World Application — Timetable Scheduling

Problem Setup

Step 1: Build candidate domains (capacity filtering)

Step 2: Neighbor graph (everyone potentially conflicts with everyone)

Step 3: Constraint predicate (room, instructor, forbidden pairs)

Step 4: Build CSP and solve (reuse solver from Section 3)

Step 5: Pretty-print the schedule

Quick Reference: Full Code

Strengths & Limitations

Strengths

Limitations

Final Notes

References

Share this:

Leave a comment Cancel reply