Project 6: Map Coloring & The AC-3 Algorithm (Constraint Propagation)

Implement AC-3 constraint propagation and solve map coloring problems efficiently.

Quick Reference

Attribute Value
Difficulty Level 3: Advanced
Time Estimate 10-16 hours
Language Python
Prerequisites CSP basics, Project 5
Key Topics AC-3, constraint propagation

1. Learning Objectives

By completing this project, you will:

  1. Represent map coloring as a CSP.
  2. Implement AC-3 for arc consistency.
  3. Reduce search space with propagation.
  4. Compare backtracking with and without AC-3.
  5. Visualize color assignments.

2. Theoretical Foundation

2.1 AC-3 Algorithm

AC-3 enforces arc consistency by removing inconsistent values from variable domains.

3. Project Specification

3.1 What You Will Build

A map coloring solver that uses AC-3 to prune domains before search.

3.2 Functional Requirements

  1. Map graph representation.
  2. Domain constraints for colors.
  3. AC-3 implementation.
  4. Backtracking with propagation.
  5. Performance metrics (nodes, time).

3.3 Non-Functional Requirements

  • Deterministic results.
  • Readable output for assignments.
  • Configurable color sets.

4. Solution Architecture

4.1 Components

Component Responsibility
CSP Model Graph + domains
AC-3 Enforce arc consistency
Solver Backtracking search
Reporter Metrics + visuals

5. Implementation Guide

5.1 Project Structure

SYMBOLIC_AI_AND_EXPERT_SYSTEMS_MASTERY/P06-map-coloring/
├── src/
│   ├── model.py
│   ├── ac3.py
│   ├── solver.py
│   └── report.py

5.2 Implementation Phases

Phase 1: CSP model (3-4h)

  • Represent map and domains.
  • Checkpoint: constraints validated.

Phase 2: AC-3 (4-6h)

  • Implement arc consistency.
  • Checkpoint: domains pruned.

Phase 3: Search + metrics (3-6h)

  • Solve with propagation.
  • Checkpoint: performance compared.

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit AC-3 domain pruning
Integration solver solves map
Regression metrics stable counts

6.2 Critical Test Cases

  1. AC-3 removes inconsistent colors.
  2. Solver finds valid coloring.
  3. Propagation reduces node expansions.

7. Common Pitfalls & Debugging

Pitfall Symptom Fix
Over-pruning no solution check constraints
No pruning AC-3 ineffective verify arc queue
Slow search high nodes add MRV heuristic

8. Extensions & Challenges

Beginner

  • Add more map datasets.
  • Add color count tuning.

Intermediate

  • Add heuristics (MRV, degree).
  • Add visualization of propagation.

Advanced

  • Add constraint learning.
  • Compare with SAT solvers.

9. Real-World Connections

  • Scheduling uses constraint propagation.
  • Resource allocation maps to coloring problems.

10. Resources

  • CSP and AC-3 references
  • Graph coloring tutorials

11. Self-Assessment Checklist

  • I can implement AC-3.
  • I can solve map coloring with constraints.
  • I can measure propagation impact.

12. Submission / Completion Criteria

Minimum Completion:

  • AC-3 implementation + map solver

Full Completion:

  • Performance comparison report

Excellence:

  • Heuristics + visualization

This guide was generated from project_based_ideas/AI_AGENTS_LLM_RAG/SYMBOLIC_AI_AND_EXPERT_SYSTEMS_MASTERY.md.