Using an array of size \(N\) of bitsets of size \(N\).

Using a vector of size \(N\) of integer decision variables.

Using a set of cardinality \(N\) of tuples of integer decision variables.

Using a matrix of size \(N \times N\) of boolean decision variables.

Has the potential to find all feasible solutions to a combinatorial problem, or to prove that no solution exists.

Can efficiently solve NP-complete problems.

Can model any problem with a rich modeling language.

Can be extended by adding new functionality, such as new constraints, to make it more complete for the modeller.

The modeller expresses the properties (constraints) that need to be satisfied using an API or dedicated domain specific language.

The modeller is not limited to linear constraints (which they are in linear programming) or Boolean clauses (which they are in SAT).

The modeller has to implement all the steps of how a solution is to be found, using their favorite programming language.

The modeller declares the problem they want to solve by shouting into a microphone.

Iteratively executes the propagate method of all constraints until each constraint returns that no values were pruned from any variable domain. The propagate method of each constraint \(c\) is executed in every iteration, even if \(c\) only contains variables whose domains are unmodified in the current node of the search tree.

Iteratively chooses one constraint randomly to propagate and stops whenever the chosen constraint returns that no values were removed from any variable domain.

Uses a propagation Queue that only contains the constraints constraining one or more variables whose domains have been modified in the current node of the search tree. The propagate method of each constraint in the propagation Queue is executed, possibly adding additional constraints to the propagation Queue.

Executes the propagate method of each constraint exactly once.

An integer list data structure.

A HashSet data structure.

A TreeSet data structure.

A BitSet data structure.

The domains are restored using a clone mechanism: making a copy of only the domain of the variable chosen for branching and restoring the domain of that specific variable on backtrack.

In each node of the search tree, for each variable, the set of removed values is stored and they are reinserted on backtrack to that node in the search tree.

The domains are restored using a clone mechanism: making a copy of the domain of each variable before branching modifies any domain and restoring the copy on backtrack.

There is no need to restore the domains when backtracking, as the call stack of the DFS recursion deals with it automatically.