CSP Solver

A Constraint Satisfaction Problem (CSP) solver library written in Rust.

Overview

This library provides efficient algorithms and data structures for solving constraint satisfaction problems. CSPs are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations.

Variable Types: int, float, mixed constraints

Constraint Categories:

• Mathematical: +, -, *, /, %, abs(), min(), max(), sum()
• Comparison: ==, !=, <, <=, >, >= (natural syntax)
• Boolean Logic: and(), or(), not() with array syntax and([a,b,c]) and variadic syntax and(a,b,c,d)
• Global: alldiff(), allequal(), element x[y] = z, count(vars, value, count), table(vars, tuples)
• Ordering: a <= b <= c, a < b < c, a >= b >= c, a > b > c (natural between constraints)
• Cardinality: at_least(vars, value, count), at_most(vars, value, count), exactly(vars, value, count)
• Conditional: if_then(condition, constraint), if_then_else(condition, then_constraint, else_constraint)

Programmatic version of constraints

m.post(x.lt(y));                        // x < y
m.post(y.le(z));                        // y <= z
m.post(z.gt(5));                        // z > 5
m.post(x.add(y).le(z));                 // x + y <= z
m.post(y.sub(x).ge(0));                 // y - x >= 0
m.post(x.mul(y).eq(12));                // x * y == 12
m.post(z.div(y).ne(0));                 // z / y != 0

Installation

Add this to your Cargo.toml:

[dependencies]
cspsolver = "0.6.0"

Examples

cargo run --release --example sudoku
cargo run --release --example n_queens
cargo run --release --example count_demo 
cargo run --release --example table_demo
cargo run --release --example magic_square

🧩 Solving PLATINUM puzzle:
📊 Puzzle stats: 17 clues given, 64 empty cells

Puzzle:                                 Solution:
┌───────┬───────┬───────┐               ┌───────┬───────┬───────┐
│ · · · │ · · · │ · · · │               │ 9 8 7 │ 6 5 4 │ 3 2 1 │
│ · · · │ · · 3 │ · 8 5 │               │ 2 4 6 │ 1 7 3 │ 9 8 5 │
│ · · 1 │ · 2 · │ · · · │               │ 3 5 1 │ 9 2 8 │ 7 4 6 │
├───────┼───────┼───────┤               ├───────┼───────┼───────┤
│ · · · │ 5 · 7 │ · · · │               │ 1 2 8 │ 5 3 7 │ 6 9 4 │
│ · · 4 │ · · · │ 1 · · │               │ 6 3 4 │ 8 9 2 │ 1 5 7 │
│ · 9 · │ · · · │ · · · │               │ 7 9 5 │ 4 6 1 │ 8 3 2 │
├───────┼───────┼───────┤               ├───────┼───────┼───────┤
│ 5 · · │ · · · │ · 7 3 │               │ 5 1 9 │ 2 8 6 │ 4 7 3 │
│ · · 2 │ · 1 · │ · · · │               │ 4 7 2 │ 3 1 9 │ 5 6 8 │
│ · · · │ · 4 · │ · · 9 │               │ 8 6 3 │ 7 4 5 │ 2 1 9 │
└───────┴───────┴───────┘               └───────┴───────┴───────┘

📊 Statistics: 638 propagations, 54 nodes explored
🔍 Efficiency: 11.8 propagations/node

Basic Usage

use cspsolver::prelude::*;

fn main() {
    let mut m = Model::default();

    // Create variables
    let x = m.int(1, 10);       // Integer variable from 1 to 10
    let y = m.int(5, 15);       // Integer variable from 5 to 15

    // Add constraints
    post!(m, x < y);            // x must be less than y
    post!(m, x + y == int(12)); // x + y must equal 12
    
    // Solve the problem
    if let Ok(solution) = m.solve() {
        println!("x = {:?}", solution[x]);  // x = ValI(1)  
        println!("y = {:?}", solution[y]);  // y = ValI(11)
    }
}

Advanced Constraint Example

use cspsolver::prelude::*;

fn main() {
    let mut m = Model::default();
    let vars = vec![m.int(1, 5), m.int(1, 5), m.int(1, 5)];
    
    // Complex mathematical expressions
    post!(m, sum(vars.clone()) <= int(12));
    post!(m, max(vars.clone()) >= int(3));  // Maximum of vars >= 3
    post!(m, min(vars.clone()) <= int(4));  // Minimum of vars <= 4
    
    // Boolean logic with traditional syntax  
    let a = m.bool();
    let b = m.bool();
    let c = m.bool();
    let d = m.bool();
    
    post!(m, and(a, b));                    // Traditional 2-argument AND
    post!(m, or(a, b));                     // Boolean OR  
    post!(m, not(b));                       // Boolean NOT
    post!(m, and([a, b, c, d]));           // Array syntax for multiple variables
    post!(m, or(a, b, c, d));              // Variadic syntax for multiple variables
    post!(m, not([a, b, c]));              // Array NOT (applies to each variable)
    
    // Count constraints - powerful cardinality constraints
    let students = vec![m.int(1, 3), m.int(1, 3), m.int(1, 3), m.int(1, 3)]; // 4 students, 3 sections
    let section1_count = m.int(2, 2); // Exactly 2 students in section 1
    let section2_count = m.int(1, 2); // 1-2 students in section 2
    
    post!(m, count(students.clone(), int(1), section1_count)); // Count students in section 1
    post!(m, count(students, int(2), section2_count));         // Count students in section 2
    
    // Advanced cardinality constraints with precise control
    let employees = vec![m.int(1, 4), m.int(1, 4), m.int(1, 4), m.int(1, 4), m.int(1, 4)]; // 5 employees, 4 departments
    post!(m, at_least(employees.clone(), int(1), int(2)));  // At least 2 in department 1 
    post!(m, at_most(employees.clone(), int(4), int(1)));   // At most 1 in department 4
    post!(m, exactly(employees, int(2), int(2)));           // Exactly 2 in department 2
    
    // Ordering constraints for complex relationships
    let start_time = m.int(9, 17);   // 9 AM to 5 PM
    let meeting_time = m.int(9, 17); // Meeting time
    let end_time = m.int(9, 17);     // End time
    post!(m, between(start_time, meeting_time, end_time)); // start <= meeting <= end
    
    // Conditional constraints for business logic
    let is_weekend = m.int(0, 1);    // 0=weekday, 1=weekend
    let hours_open = m.int(8, 12);   // Store hours
    post!(m, if_then(is_weekend == int(1), hours_open == int(8))); // Weekend stores open 8 hours
    
    // Table constraints - express complex relationships with lookup tables
    let time = m.int(1, 4);    // Time slots: 1=9AM, 2=11AM, 3=1PM, 4=3PM
    let room = m.int(1, 3);    // Rooms: 1=Lab, 2=Classroom, 3=Auditorium
    let capacity = m.int(10, 100); // Room capacity
    
    // Room availability and capacity table: (time, room, capacity)
    let schedule_table = vec![
        vec![int(1), int(1), int(20)],  // 9AM: Lab has 20 capacity
        vec![int(1), int(2), int(30)],  // 9AM: Classroom has 30 capacity
        vec![int(2), int(2), int(30)],  // 11AM: Classroom has 30 capacity  
        vec![int(2), int(3), int(100)], // 11AM: Auditorium has 100 capacity
        vec![int(3), int(1), int(20)],  // 1PM: Lab has 20 capacity
        vec![int(4), int(3), int(100)], // 3PM: Auditorium has 100 capacity
        // Note: Some time/room combinations unavailable (maintenance, etc.)
    ];
    post!(m, table([time, room, capacity], schedule_table));
    
    // Mixed type constraints with float
    let float_var = m.float(1.0, 10.0);
    post!(m, abs(float_var) <= float(12.0));
    
    if let Ok(solution) = m.solve() {
        println!("Solution found!");
    }
}

License

This project is licensed under the MIT License - see the LICENSE file for details.