Crate farc3 

A semi-generic approach to solving Constraint Satisfaction Problems,
with the possibility to optimise based on the specific implementation of Constraints.

The primary exports of this crate are:

• System for generic constraint solving
• the Assignment trait for assigning values to variables
• the Constraint trait for constraining the values variables can take
• the Heuristic trait for deciding search order for constraint solving

There’s also some common variants of constraints:

• DiscreteConstraint that covers most forms of discrete constraints
• MineConstraint that can be used for minesweeper mine solving

Examples

use farc3::prelude::*;

// Construct the two mine constraints:
// 1. 2 mines among tiles 0, 1 and 2
// 2. 1 mine among tiles 1 and 2
let constraint_0 = MineConstraint::new([0, 1, 2], 2);
let constraint_1 = MineConstraint::new([1, 2], 1);

// Construct the constraint system from these 2 constraints
let mut sys = System::from([
  constraint_0,
  constraint_1
]);

// Find all solutions to the system
let sltns: HashSet<_> = sys.solve().collect();

// All solutions should mark tile 0 as a mine
// as only one of 1 and 2 can be a mine
assert_eq!(
  sltns,
  HashSet::from([
    MineAssignment::new(/*safe*/ [1], /*mines*/ [2, 0]),
    MineAssignment::new(/*safe*/ [2], /*mines*/ [1, 0]),
  ])
);

Modules

assignment

Traits for defining assignments to variables

constraint

Traits for constraining values that variables can take

heuristics

Traits for informing which constraints to explore first in a search

prelude

Common imports to farc3-csp

system

A generic constraint solving algorithm for a system of constraints

systems

Example constraints and assignments for constraint satisfaction problems