# [−][src]Crate pcp

Constraint programming is a declarative programming paradigm mainly used to solve combinatorial problems where you state what constraints a solution must fullfil instead of explaining how to solve it (see README.md). A very classic introductory problem to constraint programming is the N-Queens puzzle: the goal is to align N queens on a chessboard of size N*N such that no queen can attack each other. In PCP, we can solve this problem as follows:

```extern crate pcp;
extern crate gcollections;
extern crate interval;
use pcp::kernel::*;
use pcp::propagators::*;
use pcp::variable::ops::*;
use pcp::term::*;
use pcp::search::search_tree_visitor::Status::*;
use pcp::search::*;
use pcp::concept::*;
use interval::ops::Range;
use interval::interval_set::*;
use gcollections::ops::*;

pub fn nqueens(n: usize) {
let mut space = FDSpace::empty();

let mut queens = vec![];
// 2 queens can't share the same line.
for _ in 0..n {
queens.push(Box::new(space.vstore.alloc(IntervalSet::new(1, n as i32))) as Var<VStore>);
}
for i in 0..n-1 {
for j in i + 1..n {
// 2 queens can't share the same diagonal.
let q1 = (i + 1) as i32;
let q2 = (j + 1) as i32;
// Xi + i != Xj + j reformulated as: Xi != Xj + j - i
space.cstore.alloc(Box::new(XNeqY::new(
queens[i].bclone(), Box::new(Addition::new(queens[j].bclone(), q2 - q1)) as Var<VStore>)));
// Xi - i != Xj - j reformulated as: Xi != Xj - j + i
space.cstore.alloc(Box::new(XNeqY::new(
queens[i].bclone(), Box::new(Addition::new(queens[j].bclone(), -q2 + q1)) as Var<VStore>)));
}
}
// 2 queens can't share the same column.
// join_distinct(&mut space.vstore, &mut space.cstore, queens);
space.cstore.alloc(Box::new(Distinct::new(queens)));

// Search step.
let mut search = one_solution_engine();
search.start(&space);
let (frozen_space, status) = search.enter(space);
let space = frozen_space.unfreeze();

// Print result.
match status {
Satisfiable => {
print!("{}-queens problem is satisfiable. The first solution is:\n[", n);
for dom in space.vstore.iter() {
// At this stage, dom.lower() == dom.upper().
print!("{}, ", dom.lower());
}
println!("]");
}
Unsatisfiable => println!("{}-queens problem is unsatisfiable.", n),
EndOfSearch => println!("Search terminated or was interrupted."),
Unknown(_) => unreachable!(
"After the search step, the problem instance should be either satisfiable or unsatisfiable.")
}
}

fn main() {
nqueens(8);
}```

## Modules

 concept kernel The kernel is a set of reusable traits shared among the different modules. It does not provide specific implementations. logic model propagation Propagation is a set of algorithmic components to verify the consistency of a constraint conjunction, called the constraints store. propagators Propagators are implementations of constraints, a single constraint can be realized by different propagators. search The search explores a tree where nodes are a couple of variables and constraints store, called a space. The tree is constructed during the search and backtracking occurs when a node is failed (it does not lead to a solution). The exploration of the tree can be customized by different heuristics combined with search combinators implemented with `SearchTreeVisitor`. term variable A variable is a pair `(location, value)` where the value lives inside a block of memory, called the variables store. The store is parametrized by the type of the values it will contain, it is the domain of the variables.