pcp/
lib.rs

1// Copyright 2015 Pierre Talbot (IRCAM)
2
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6
7//     http://www.apache.org/licenses/LICENSE-2.0
8
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! 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).
16//! A very classic introductory problem to constraint programming is the [N-Queens puzzle](https://en.wikipedia.org/wiki/Eight_queens_puzzle): the goal is to align N queens on a chessboard of size N*N such that no queen can attack each other.
17//! In PCP, we can solve this problem as follows:
18//! ```rust
19//! extern crate pcp;
20//! extern crate gcollections;
21//! extern crate interval;
22//! use pcp::kernel::*;
23//! use pcp::propagators::*;
24//! use pcp::variable::ops::*;
25//! use pcp::term::*;
26//! use pcp::search::search_tree_visitor::Status::*;
27//! use pcp::search::*;
28//! use pcp::concept::*;
29//! use interval::ops::Range;
30//! use interval::interval_set::*;
31//! use gcollections::ops::*;
32//!
33//! pub fn nqueens(n: usize) {
34//!   let mut space = FDSpace::empty();
35//!
36//!   let mut queens = vec![];
37//!   // 2 queens can't share the same line.
38//!   for _ in 0..n {
39//!     queens.push(Box::new(space.vstore.alloc(IntervalSet::new(1, n as i32))) as Var<VStore>);
40//!   }
41//!   for i in 0..n-1 {
42//!     for j in i + 1..n {
43//!       // 2 queens can't share the same diagonal.
44//!       let q1 = (i + 1) as i32;
45//!       let q2 = (j + 1) as i32;
46//!       // Xi + i != Xj + j reformulated as: Xi != Xj + j - i
47//!       space.cstore.alloc(Box::new(XNeqY::new(
48//!         queens[i].bclone(), Box::new(Addition::new(queens[j].bclone(), q2 - q1)) as Var<VStore>)));
49//!       // Xi - i != Xj - j reformulated as: Xi != Xj - j + i
50//!       space.cstore.alloc(Box::new(XNeqY::new(
51//!         queens[i].bclone(), Box::new(Addition::new(queens[j].bclone(), -q2 + q1)) as Var<VStore>)));
52//!     }
53//!   }
54//!   // 2 queens can't share the same column.
55//!   // join_distinct(&mut space.vstore, &mut space.cstore, queens);
56//!   space.cstore.alloc(Box::new(Distinct::new(queens)));
57//!
58//!   // Search step.
59//!   let mut search = one_solution_engine();
60//!   search.start(&space);
61//!   let (frozen_space, status) = search.enter(space);
62//!   let space = frozen_space.unfreeze();
63//!
64//!   // Print result.
65//!   match status {
66//!     Satisfiable => {
67//!       print!("{}-queens problem is satisfiable. The first solution is:\n[", n);
68//!       for dom in space.vstore.iter() {
69//!         // At this stage, dom.lower() == dom.upper().
70//!         print!("{}, ", dom.lower());
71//!       }
72//!       println!("]");
73//!     }
74//!     Unsatisfiable => println!("{}-queens problem is unsatisfiable.", n),
75//!     EndOfSearch => println!("Search terminated or was interrupted."),
76//!     Unknown(_) => unreachable!(
77//!       "After the search step, the problem instance should be either satisfiable or unsatisfiable.")
78//!   }
79//! }
80//!
81//! fn main() {
82//!  nqueens(8);
83//! }
84//! ```
85
86extern crate trilean;
87extern crate interval;
88extern crate gcollections;
89extern crate num;
90extern crate vec_map;
91extern crate bit_set;
92
93pub mod kernel;
94pub mod logic;
95pub mod propagation;
96pub mod propagators;
97pub mod term;
98pub mod variable;
99pub mod search;
100pub mod concept;
101pub mod model;
pcp/lib.rs

pcp/
lib.rs
