AC-3rm

A highly efficient incremental Arc Consistency (AC-3rm) propagator written in Rust.

AC-3rm maintains constraint consistency dynamically, supporting:

• Dynamic constraint insertion with incremental propagation
• Dynamic constraint retraction with neighborhood re-propagation
• AC-3rm algorithm with residual supports for optimal constraint checking
• Batch operations for efficient multi-constraint updates
• Listener callbacks for reactive domain change notifications

Constraint Types

• Binary equality: var_a == var_b
• Binary inequality: var_a != var_b
• Unary set: var == value (domain becomes singleton)
• Unary forbid: var != value (value removed from domain)

Key Features

AC-3rm with Residual Supports

The engine implements the AC-3rm algorithm, which extends AC-3 with residual supports:

• Each value maintains a cached support to avoid redundant domain scans
• When a domain changes, only affected arcs are re-queued
• Incoming arcs are prioritized during propagation for efficiency

Incremental Architecture

• Constraints can be added and removed dynamically
• Retracting a constraint only re-propagates the affected neighborhood
• Multi-killer support: values can be suppressed by multiple constraints simultaneously

Batch Operations

For better performance when applying multiple constraints:

• assert_batch(&[id1, id2, ...]) — Assert multiple constraints with a single propagation pass
• retract_batch(&[id1, id2, ...]) — Retract multiple constraints with a single re-propagation pass

Reactive Updates

Register callbacks to monitor domain changes in real-time:

engine.set_listener(var_id, |var| {
    println!("Variable {} domain changed", var);
});

Installation

Add to Cargo.toml:

[dependencies]
ac3rm = "0.1"

Usage

Basic Constraint Propagation

use ac3rm::Engine;

fn main() -> Result<(), ac3rm::PropagationError> {
    let mut engine = Engine::new();

    // Create variables
    let a = engine.add_var([1, 2, 3]);
    let b = engine.add_var([2, 3, 4]);

    // Add equality constraint
    engine.new_eq(a, b)?;

    // Domains are now intersected: {2, 3}
    assert_eq!(engine.val(a), vec![2, 3]);
    assert_eq!(engine.val(b), vec![2, 3]);

    Ok(())
}

Dynamic Constraint Retraction

use ac3rm::Engine;

fn main() -> Result<(), ac3rm::PropagationError> {
    let mut engine = Engine::new();
    let a = engine.add_var([1, 2, 3]);
    let b = engine.add_var([2, 3, 4]);

    let eq_id = engine.new_eq(a, b)?;
    assert_eq!(engine.val(a), vec![2, 3]);

    // Remove the constraint
    engine.retract(eq_id)?;

    // Domains return to original state
    assert_eq!(engine.val(a), vec![1, 2, 3]);
    assert_eq!(engine.val(b), vec![2, 3, 4]);

    Ok(())
}

Batch Operations

use ac3rm::{Constraint, Engine};

fn main() -> Result<(), ac3rm::PropagationError> {
    let mut engine = Engine::new();
    let x = engine.add_var([1, 2, 3]);
    let y = engine.add_var([1, 2, 3]);

    let c1 = engine.add_constraint(Constraint::Equality(x, y));
    let c2 = engine.add_constraint(Constraint::Set(x, 2));
    let c3 = engine.add_constraint(Constraint::Forbid(y, 1));

    // Apply all three constraints with a single propagation pass
    engine.assert_batch(&[c1, c2, c3])?;

    Ok(())
}

Listener Callbacks

use ac3rm::Engine;
use std::sync::{Arc, Mutex};

fn main() -> Result<(), ac3rm::PropagationError> {
    let mut engine = Engine::new();
    let x = engine.add_var([1, 2, 3]);
    let y = engine.add_var([2, 3, 4]);

    let changes = Arc::new(Mutex::new(Vec::new()));
    let changes_clone = changes.clone();

    engine.set_listener(x, move |var_id| {
        changes_clone.lock().unwrap().push(var_id);
    });

    engine.new_eq(x, y)?; // Triggers listener callback

    Ok(())
}

Error Handling

use ac3rm::PropagationError;

match engine.new_eq(a, b) {
    Ok(id) => println!("Constraint {} asserted", id),
    Err(PropagationError::DomainWipeout { var, explanation }) => {
        println!("Variable {} has no valid values", var);
        println!("Conflicting constraints: {:?}", explanation);
    }
    Err(PropagationError::InvalidConstraintId(id)) => {
        println!("Constraint {} does not exist", id);
    }
}

Performance Characteristics

• Assertion: O(d·k) in worst case, where d is domain size, k is arity (≤2 for this engine)
• Retraction: O(d·k) incremental re-propagation of affected neighborhood
• Residual supports: Amortized O(1) support lookup in typical scenarios

Testing

All functionality is thoroughly tested:

cargo test --lib

Tests cover:

• Unary and binary constraint interactions
• Incremental retraction and re-assertion
• Multi-killer scenarios (multiple constraints suppressing the same value)
• Batch operation equivalence with sequential calls
• Listener notification during propagation
• Complex propagation chains

Architecture

The engine manages:

• Variables: Each has a domain of active/suppressed values
• Constraints: Can be active (enforced) or inactive
• Residues: Cached support values for AC-3rm optimization
• Listeners: Callbacks invoked when domains change

The propagation queue processes arcs (directed constraint applications) until quiescence, ensuring arc-consistency is maintained after each update.