Problems

Modelling a problem to be solved consists in instantiating a Problem. While it is very common to start from scratch, it is also possible to subclass some pre-defined problems.

The constructor of the Problem class

The constructor of Problem accepts a single argument: the domains as a list of pairs of integers (if the minimal and maximal values of the pair are equal, the pair can be replaced by the value).

Python, with the help of lists and ranges, makes the construction of complex problems an easy task.

Propagators are then added to the problem with the use of the add_propagator method.

A concrete example: the 4-queens problem

4-queens image

4 non attacking queens

The 4-queens problem can be modelled as follows:

  • for \(i\) in \([0, 3]\), \(v_i\) is the vertical position of the queen in the \(i\) th column

  • \(v_0, v_1, v_2, v_3\) are all different

  • \(v_0, v_1 + 1, v_2 + 2, v_3 + 3\) are all different

  • \(v_0, v_1 - 1, v_2 - 2, v_3 - 3\) are all different

In NuCS, the n-queens problem is indeed constructed as follows:

def __init__(self, n: int):
   super().__init__([(0, n - 1)] * n)
   variables = range(0, n)
   self.add_propagator(ALG_ALLDIFFERENT, variables)
   self.add_propagator(ALG_ALLDIFFERENT, variables, range(n))
   self.add_propagator(ALG_ALLDIFFERENT, variables, range(0, -n, -1))