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

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

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

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

Can model any problem with a rich modeling language.

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

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

Can efficiently solve NP-complete problems.

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

The modeller has to implement all the steps of how a solution is to be found, using their favorite programming 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 declares the problem they want to solve by shouting into a microphone.

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

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.

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 BitSet data structure.

A TreeSet 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.

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

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.