1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

// Copyright 2015 Pierre Talbot (IRCAM)

// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at

//     http://www.apache.org/licenses/LICENSE-2.0

// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

//! 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`.

pub mod space;
pub mod recomputation;
pub mod branching;
pub mod search_tree_visitor;
pub mod propagation;
pub mod engine;
pub mod monitor;
pub mod statistics;
pub mod branch_and_bound;
pub mod debugger;
pub mod stop_node;

pub use search::space::*;
pub use search::search_tree_visitor::*;

use propagation::CStoreFD;
use variable::VStoreSet;
use search::engine::one_solution::*;
use search::branching::*;
use search::propagation::*;
use gcollections::VectorStack;

pub type VStore = VStoreSet;
type CStore = CStoreFD<VStore>;
pub type FDSpace = Space<VStore, CStore, NoRecomputation<VStore, CStore>>;

pub fn one_solution_engine() -> Box<dyn SearchTreeVisitor<FDSpace>> {
  let search =
    OneSolution::<_, VectorStack<_>, FDSpace>::new(
    Propagation::new(
    Brancher::new(FirstSmallestVar, MiddleVal, BinarySplit)));
  Box::new(search)
}

#[cfg(test)]
mod test {
  pub use super::*;
  use propagators::cmp::*;
  use propagators::distinct::*;
  use term::*;
  use gcollections::ops::*;
  use interval::interval_set::*;
  use concept::*;

  pub fn nqueens(n: usize, space: &mut FDSpace) {
    let mut queens: Vec<Var<VStore>> = vec![];
    // 2 queens can't share the same line.
    for _ in 0..n {
      queens.push(Box::new(space.vstore.alloc((1, n as i32).to_interval_set())));
    }
    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
        space.cstore.alloc(Box::new(XNeqY::new(queens[i].bclone(), Box::new(Addition::new(queens[j].bclone(), q2 - q1)))));
        // Xi - i != Xj - j
        space.cstore.alloc(Box::new(XNeqY::new(queens[i].bclone(), Box::new(Addition::new(queens[j].bclone(), -q2 + q1)))));
      }
    }
    // 2 queens can't share the same column.
    space.cstore.alloc(Box::new(Distinct::new(queens)));
  }
}