OpenParable
Skip to content
← Back to skills

Constraint Satisfaction Solver

Development
constraint-satisfaction-solver

Constraint Satisfaction Solver is an Agent Skill for development published in the a5c-ai/babysitter repository on GitHub: a SKILL.md instruction file an AI agent can load to do this task.

Constraint programming skill for scheduling, configuration, and assignment problems

View on GitHub ↗
QUICK START

How to use this skill

Bring this guide into your coding agent with a prompt tailored to the tool you use.

  1. Open your project in Codex.
  2. Copy and paste the prompt below.
  3. Review files and risks before approving any action.
Prompt to paste
Inspect the Agent Skill at https://github.com/a5c-ai/babysitter/blob/HEAD/library/specializations/domains/business/decision-intelligence/skills/constraint-satisfaction-solver/SKILL.md and all supporting files. Report provenance, permissions, scripts, dependencies, and security risks. Propose an exact installation into .agents/skills/constraint-satisfaction-solver, but wait for my approval before writing files or running scripts.

Copying this prompt does not install or run the skill. Review third-party files before use.

Constraint Satisfaction Solver

Overview

The Constraint Satisfaction Solver skill provides capabilities for solving constraint satisfaction problems (CSPs) and constraint optimization problems (COPs). It excels at scheduling, configuration, assignment, and combinatorial problems where finding feasible solutions is as important as optimization.

Capabilities

  • Variable and domain definition
  • Constraint specification (global constraints)
  • Solution search strategies
  • Optimization with constraints
  • Scheduling constraint handling
  • Configuration problem solving
  • All-solutions enumeration
  • Constraint propagation explanation

Used By Processes

  • Prescriptive Analytics and Optimization
  • Resource Scheduling
  • Operational Decisions

Usage

Problem Definition

# Define CSP
csp_problem = {
    "name": "Employee Scheduling",
    "variables": {
        "shift_mon_morning": {"domain": ["Alice", "Bob", "Carol", "David"]},
        "shift_mon_afternoon": {"domain": ["Alice", "Bob", "Carol", "David"]},
        "shift_tue_morning": {"domain": ["Alice", "Bob", "Carol", "David"]},
        "shift_tue_afternoon": {"domain": ["Alice", "Bob", "Carol", "David"]},
        # ... more shifts
    },
    "constraints": [
        {
            "type": "all_different",
            "scope": ["shift_mon_morning", "shift_mon_afternoon"],
            "description": "Different employees on same day"
        },
        {
            "type": "not_equal",
            "variables": ["shift_mon_afternoon", "shift_tue_morning"],
            "condition": "employee",
            "description": "No back-to-back closing/opening"
        },
        {
            "type": "count",
            "variable": "Alice",
            "min": 3,
            "max": 5,
            "description": "Alice works 3-5 shifts per week"
        }
    ]
}

Scheduling Constraints

# Job shop scheduling
scheduling_problem = {
    "jobs": [
        {
            "id": "Job1",
            "tasks": [
                {"id": "J1_T1", "machine": "M1", "duration": 3},
                {"id": "J1_T2", "machine": "M2", "duration": 2, "after": "J1_T1"}
            ]
        },
        {
            "id": "Job2",
            "tasks": [
                {"id": "J2_T1", "machine": "M2", "duration": 2},
                {"id": "J2_T2", "machine": "M1", "duration": 3, "after": "J2_T1"}
            ]
        }
    ],
    "constraints": {
        "no_overlap": "tasks on same machine cannot overlap",
        "precedence": "tasks must respect ordering within job",
        "deadline": {"Job1": 10, "Job2": 8}
    },
    "objective": "minimize_makespan"  # or "minimize_tardiness"
}

Configuration Problem

# Product configuration
config_problem = {
    "components": {
        "engine": {"options": ["V6", "V8", "Electric"]},
        "transmission": {"options": ["Manual", "Automatic", "CVT"]},
        "wheel_size": {"options": [17, 18, 19, 20]},
        "color": {"options": ["Red", "Blue", "Black", "White"]}
    },
    "constraints": [
        {
            "type": "implication",
            "if": {"engine": "Electric"},
            "then": {"transmission": ["Automatic", "CVT"]},
            "description": "Electric engines don't support manual transmission"
        },
        {
            "type": "incompatible",
            "values": [{"engine": "V6"}, {"wheel_size": 20}],
            "description": "V6 not available with 20-inch wheels"
        }
    ]
}

Global Constraints

ConstraintDescriptionExample Use
AllDifferentAll variables take distinct valuesSudoku, assignment
CumulativeResource usage over timeScheduling
CircuitVariables form a Hamiltonian circuitTSP, routing
TableAllowed/forbidden combinationsConfiguration
RegularSequence matches automatonShift patterns
CardinalityCount of value occurrencesWorkload balance

Input Schema

{
  "problem_type": "csp|cop|scheduling|configuration",
  "variables": {
    "var_name": {
      "domain": "array or range",
      "type": "integer|boolean|set"
    }
  },
  "constraints": [
    {
      "type": "string",
      "scope": ["string"],
      "parameters": "object"
    }
  ],
  "objective": {
    "type": "minimize|maximize",
    "expression": "string"
  },
  "search_config": {
    "strategy": "default|first_fail|min_domain",
    "time_limit": "number",
    "all_solutions": "boolean",
    "max_solutions": "number"
  }
}

Output Schema

{
  "status": "Satisfied|Optimal|Infeasible|Unknown",
  "solution": {
    "variable_name": "value"
  },
  "objective_value": "number (if COP)",
  "all_solutions": [
    {"variable_name": "value"}
  ],
  "statistics": {
    "nodes_explored": "number",
    "propagations": "number",
    "backtracks": "number",
    "solve_time": "number"
  },
  "explanation": {
    "unsatisfied_constraints": ["string"],
    "conflict_set": ["string"]
  }
}

Search Strategies

StrategyDescriptionBest For
First FailChoose variable with smallest domainGeneral CSPs
Min DomainSame as first failGeneral CSPs
ImpactChoose by constraint propagation impactLarge problems
ActivityChoose frequently changed variablesRestart searches
RandomRandom variable/value selectionDiversification

Best Practices

  1. Define tight domains to reduce search space
  2. Use appropriate global constraints (more efficient than decomposed)
  3. Add redundant constraints to improve propagation
  4. Consider symmetry breaking constraints
  5. Use restarts for large, hard problems
  6. Profile to identify propagation bottlenecks
  7. Validate solutions against business requirements

Integration Points

  • Connects with Linear Programming Solver for hybrid approaches
  • Feeds into Optimization Specialist agent
  • Supports Scheduling and Assignment processes
  • Integrates with Decision Visualization for Gantt charts