Trait Constraint

Source

pub trait Constraint {
    type Var;
    type Solution: Assignment;
    type ConflictErr: Debug;

    // Required methods
    fn size(&self) -> usize;
    fn variables(&self) -> impl Iterator<Item = Self::Var>;
    fn decompositions(&self) -> impl Iterator<Item = Self>;
    fn reduce(&mut self, other: &Self) -> Result<bool, Self::ConflictErr>;
    fn pop_solution(&mut self) -> Option<Self::Solution>;
}

Expand description

A constraint that affects given variables in a system
A given constriant can be satisfied by multiple possible assignments.

§Invariants

if self.variables().count() == 0, then self.size() == 1
i.e. if a constraint affects no variables, it should have 1 solution, the empty solution
if this.variables().count() > 0, then this.decompositions().count() >= 1
i.e. if a constraint affects any variables, it should have at least 1 decomposition

§Formal definition

Formally, a constraint is a set of possible assignments for the variables within a problem.

For example, in a minesweeper game:

the variables would be [x, y] positions for a tile
the values to assign would be true/false for whether a mine is in a tile

And a possible constraint could be:

{
  { [2, 3]: true, [3, 3]: false },
  // position [2, 3] is a mine
  // position [3, 3] is safe

  // or

  { [2, 3]: false, [3, 3]: true },
  // position [2, 3] is safe
  // position [3, 3] is a mine
}

Required Associated Types§

Source

type Var

The type of variables assigned by the Constraint

Source

type Solution: Assignment

Any solution to a Constraint

Source

type ConflictErr: Debug

The error raised when 2 constraints conflict with each other

Required Methods§

Source

fn size(&self) -> usize

An approximation to the number of unique assignments that self has.

This doesn’t have to be exact, but should at least:

return 1 when there’s only one unique solution
return 0 when no solutions are possible

Source

fn variables(&self) -> impl Iterator<Item = Self::Var>

All variables that self affects

Source

fn decompositions(&self) -> impl Iterator<Item = Self>

Possible decompositions for this constraint.

A decomposition is a constraint that:

affects a subset of self.variables()
has a single unique solution that self allows

§Returns

An iterator over the possible decompositions of self

Source

fn reduce(&mut self, other: &Self) -> Result<bool, Self::ConflictErr>

Removes the overlap between another constraint and this one.
This is useful as it lets us remove uncertainty from the system
and make it simpler to solve.