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.