Constraint Satisfaction Problem formulation

Question

I am given the following requirements which need to be formulated into a CSP problem by defining a set of variables, and a set of constraints over those variables. However I'm having trouble formulating the constraints and variables for my problem.

Some info: The solution to the problem is a list of assignments: [Var, A1, A2, A3] where Var is the variable and A1, A2, A3 is an ordered sequence of valid assignments.

Requirements:

• Each variable is assigned a value in problem.valid_assignments()
• Each variable's first assignment is in problem.first_assignments()
• Each variable's assignment sequence is in problem.valid_pairs() (Some assignments can't follow others)
• Given an integer K, there can be no more than K continuous assignments where at least one is not in problem.k_assignment()
• Every value in the given assignments list: problem.assignment must be used.

Available Constraints:

• NValues constraint: Given a list of required_values, an upper bound and lower bound, makes sure that the number of variables whose value is in required_values is between the bounds.
• AllDifferent constraint: Given a set of variables, enforces their inequality. That is no two variables in the set are equal.
• NotEqual constraints: Given Var1, Var2, enforces: Var1 != Var2

So Far:

• A Variable for each Var whose domain is problem.valid_assignments()
• A Variable for each Var whose domain is problem.first_assignments()
• A NValues constraint for each Var whose scope is [Var], required values problem.valid_assignments(Var), lower bound 0, upper bound len(domain).

Additional info:

• The solution is a "list of assignments" as in for each Var we return [Var, A1, A2, A3] where Var is the variable assigned and A1 through A3 are valid assignments that fulfil the given constraints. The exact format doesn't matter as I'm only looking for a conceptual solution. Additionally A1, A2, A3 (aka all assignments for a Var) must obviously be in the domain of that variable. (Domains can overlap between variables).

• valid_pairs() returns a list of tuples [(A1, A2), (A2,A3)]. The constraint is such that the returned solution list (as detailed above) must have consecutive assignments that form valid pairs that are given by this function. For example if the solution is [Var, A1, A2, A4, A3] and the valid pairs are [(A1, A2), (A2,A3)] then the solution is incorrect as (A2, A4) (A4, A3) is not in the list ((A1, A2) however is a valid pair).

• Essentially we're looking for arc-consistency.

Answer 1

• We can use an NValues constraint whose scope is all variables, and domain is each possible assignment (For each assignment create a constraint). This ensures that all values are assigned when set to have an upper and lower bound of 1.

• We can use use Neq constraint with a bit of modification to ensure the correct sequencing by feeding it tuples of valid assignments.

• We can again use NValues constraint to ensure the k_assignment requirement by passing a lower bound of 1, and upper bound of K with domain K_assignments.

• In the same way we can use NValues constraint with domain problem.first_assignments() for the first assignment. And another with domain problem.valid_assignments() to fill in the blanks.