Backtracking

And therefore it must have been registered beforehand.

And we must be able to rebut a decision.

Search strategy

How to select the next decision to apply?

select an uninstantiated variable
pick a value in its domain (e.g., the lower bound)

A recursive approach should simplify our task

Let’s break down the needs into 4 functions.

def make_decision(variables):
    pass

def copy_domains(variables):
    pass

def apply_decision(variables, var, val, apply, constraint):
    pass

def dfs(variables, constraint):
    pass

>>🥛<<

def make_decision(variables):
    var, dom = next(
        filter(lambda x: len(x[1]) > 1, variables.items()),
        (None, None))
    if var is not None:
        # if true, returns the decision
        return (var, min(dom))
    else:
        # otherwise, all variables are instantiated
        return None

def copy_domains(variables):
    # returns a deep copy of the dictionnary
    return {var: dom.copy() for var, dom in variables.items()}

def apply_decision(variables, var, val, apply, constraint):
  # copy the domains
  c_variables = copy_domains(variables)
  # applies the decision or rebuts is
  c_variables[var] = {x for x in c_variables[var] \
                      if apply is (x == val)}
  # explore the sub-branch
  return dfs(c_variables, constraint)

def dfs(variables, constraint):
  constraint.filter(variables)
  dec = make_decision(variables)
  if dec is None:
      print(variables)  # prints the solution
      return 1
  else:
      var, val = dec
      n = apply_decision(variables, var, val, True, constraint)
      n += apply_decision(variables, var, val, False, constraint)
  return n

variables = {"x1": {1, 2, 3},
             "x2": {1, 2, 3}}
c1 = LessThan("x1", "x2")

print("There are", dfs(variables, c1), "solutions")

should output:

{'x1': {1}, 'x2': {2}}
{'x1': {1}, 'x2': {3}}
{'x1': {2}, 'x2': {3}}
There are 3 solutions

We did it !

Well almost, but still you can pat yourself back !