# 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)`
**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`:
```toml
[dependencies]
cspsolver = "0.6.0"
```
## 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
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
```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!");
}
}
```
## License
This project is licensed under the MIT License - see the [LICENSE](LICENSE) file for details.