#combinatorial #constraint #csp

rust-constraint

Rust implementation of a constraint satisfaction problem (CSPs)

1 unstable release

0.1.0-alpha.1 Jul 2, 2024

#4 in #csp

MIT license

12KB
271 lines

Constraint Satisfaction Problem (CSPs)

This crate is ideal for solving scheduling problems, graph coloring, and other CSPs where variables need to be assigned values under specific constraints.

Useful for educational purposes, AI projects, and any application requiring formal logical reasoning.

Example

In this context, the variables A, B, C, etc., represent different classes that need to be scheduled on specific days of the week (Monday, Tuesday, Wednesday) while ensuring that certain classes do not occur on the same day.

use rust_constraint::prelude::*;

let mut problem: Problem<&str> = Problem::new().variables(
    vec!["A", "B", "C", "D", "E", "F", "G"],
    vec!["Monday", "Tuesday", "Wednesday"],
);

let constraints = vec![
    ("A", "B"),
    ("A", "C"),
    ("B", "C"),
    ("B", "D"),
    ("B", "E"),
    ("C", "E"),
    ("C", "F"),
    ("D", "E"),
    ("E", "F"),
    ("E", "G"),
    ("F", "G"),
];

for (x, y) in constraints {
    problem.add_constraint_binary(x, y, |x, y| x != y)
}

for solution in problem.get_solutions() {
    println!("{solution}")
}

Output

{B: Tuesday, F: Tuesday, G: Wednesday, E: Monday, D: Wednesday, A: Monday, C: Wednesday}
{B: Wednesday, F: Wednesday, G: Tuesday, E: Monday, D: Tuesday, A: Monday, C: Tuesday}
{B: Monday, F: Monday, G: Wednesday, E: Tuesday, D: Wednesday, A: Tuesday, C: Wednesday}
{B: Wednesday, F: Wednesday, G: Monday, E: Tuesday, D: Monday, A: Tuesday, C: Monday}
{B: Monday, F: Monday, G: Tuesday, E: Wednesday, D: Tuesday, A: Wednesday, C: Tuesday}
{B: Tuesday, F: Tuesday, G: Monday, E: Wednesday, D: Monday, A: Wednesday, C: Monday}

Source: CS50

Acknowledgments

Inspired by: python-constraint used in CS50’s Introduction to Artificial Intelligence with Python.

No runtime deps