# CSP Solver
[](https://crates.io/crates/cspsolver)
[](https://docs.rs/cspsolver)
[](https://opensource.org/licenses/MIT)
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)`
## Installation
Add this to your `Cargo.toml`:
```toml
[dependencies]
cspsolver = "0.5.17"
```
## Examples
```bash
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
```rust
use cspsolver::prelude::*;
fn main() {
let mut m = Model::default();
// Create variables with clean syntax
let x = m.int(1, 10); // Integer variable
let y = m.int(5, 15); // Integer variable
let z = m.int(0, 20); // Integer variable for array compatibility
// Mathematical constraints using post! macro
post!(m, x < y); // Comparison
post!(m, x + y >= int(10)); // Arithmetic
post!(m, abs(z) <= int(15)); // Math functions
// Enhanced constraint features
post!(m, sum([x, y]) == int(12)); // Sum function
post!(m, x % int(3) != int(0)); // Modulo operations
// Global constraints
post!(m, alldiff([x, y])); // All different
post!(m, allequal([x, y])); // All equal
// Ordering constraints - powerful ternary relationships
post!(m, x <= y <= z); // Natural chained comparison syntax
post!(m, between(x, y, z)); // Alternative function syntax
// Cardinality constraints - counting with fine-grained control
let tasks = vec![m.int(1, 3), m.int(1, 3), m.int(1, 3)]; // 1=low, 2=medium, 3=high priority
post!(m, at_least(tasks.clone(), int(3), int(1))); // At least 1 high priority task
post!(m, at_most(tasks.clone(), int(1), int(2))); // At most 2 low priority tasks
post!(m, exactly(tasks, int(2), int(1))); // Exactly 1 medium priority task
// Conditional constraints - if-then logic
post!(m, if_then(x == int(5), y == int(10))); // If x=5 then y=10
// Count constraint - count how many variables equal a value
let workers = vec![m.int(1, 3), m.int(1, 3), m.int(1, 3)]; // 1=day, 2=evening, 3=night
let night_count = m.int(1, 2); // 1-2 workers on night shift
post!(m, count(workers, int(3), night_count)); // Count night shift workers
// Table constraint - specify valid combinations explicitly
let cpu = m.int(1, 2); // 1=Intel, 2=AMD
let gpu = m.int(1, 2); // 1=NVIDIA, 2=AMD
let compatible_configs = vec![
vec![int(1), int(1)], // Intel CPU + NVIDIA GPU
vec![int(1), int(2)], // Intel CPU + AMD GPU
vec![int(2), int(2)], // AMD CPU + AMD GPU
// Note: AMD CPU + NVIDIA GPU not included (incompatible)
];
post!(m, table([cpu, gpu], compatible_configs)); // Only valid combinations allowed
// Element constraint (array indexing)
let array = vec![x, y, z];
let index = m.int(0, 2);
let value = m.int(1, 20);
post!(m, array[index] == value); // Natural x[y] = z syntax
if let Ok(solution) = m.solve() {
println!("x = {:?}", solution[x]);
println!("y = {:?}", solution[y]);
println!("z = {:?}", solution[z]);
}
}
```
### Advanced Constraint Examples
```rust
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!");
}
}
```
### New Constraint Types (v0.5.11+)
The latest version includes powerful new constraint types for advanced modeling:
#### Between Constraints
Enforce ternary ordering relationships with natural chained comparison syntax:
```rust
let start = m.int(1, 10);
let middle = m.int(5, 15);
let end = m.int(10, 20);
// Natural chained comparison syntax (recommended)
post!(m, start <= middle <= end);
// Alternative function syntax
post!(m, between(start, middle, end));
// Other chained comparisons
post!(m, start < middle < end); // Strict inequalities
post!(m, end >= middle >= start); // Reverse order
```
#### Cardinality Constraints
Precise counting control for resource allocation and capacity planning:
```rust
let workers = vec![m.int(1, 3), m.int(1, 3), m.int(1, 3), m.int(1, 3)]; // 4 workers, 3 shifts
post!(m, at_least(workers.clone(), int(3), int(2))); // At least 2 on night shift (3)
post!(m, at_most(workers.clone(), int(1), int(1))); // At most 1 on day shift (1)
post!(m, exactly(workers, int(2), int(1))); // Exactly 1 on evening shift (2)
```
#### Conditional Constraints
Business logic and dependency modeling with if-then-else:
```rust
let weather = m.int(1, 3); // 1=sunny, 2=cloudy, 3=rainy
let activity = m.int(1, 3); // 1=hiking, 2=museum, 3=shopping
let backup = m.int(1, 3); // Backup activity
// If sunny (1) then hiking (1), if rainy (3) then shopping (3)
post!(m, if_then(weather == int(1), activity == int(1)));
post!(m, if_then(weather == int(3), activity == int(3)));
```
These constraints work seamlessly with the existing `post!` macro system and provide both helper methods and natural syntax for maximum usability.
## License
This project is licensed under the MIT License - see the [LICENSE](LICENSE) file for details.