Constraint Programming with CP Flashcards

When modeling a constraint satisfaction problem in Picat using the `cp` module, what is the primary purpose of the `solve/1` predicate?

Answer: To initiate the search process for finding a valid assignment of values to the variables.

In Picat's CP module, problem modeling involves first declaring variables and their domains (e.g., `Vars :: 0..9`), then posting constraints (e.g., `alldifferent(Vars)`, `A #> B`). The `solve/1` (or `solve/2`) predicate is called after these steps to start the search and labeling process, where the solver systematically assigns values to variables to find a solution that satisfies all posted constraints.

A developer is solving a crypto-arithmetic puzzle like `SEND + MORE = MONEY` in Picat. Which global constraint from the `cp` module is essential to ensure that each letter is assigned a unique digit?

Answer: `alldifferent/1`

The core rule of crypto-arithmetic puzzles is that each letter must represent a different digit. The `alldifferent(List)` global constraint in the `cp` module enforces exactly this, ensuring that all variables in the given list are assigned distinct values from their respective domains.

Which of the following lines of code correctly declares a list of three Picat variables `X`, `Y`, and `Z` as constraint variables, each with a domain of integers from 1 to 10, for use with the `cp` module?

Answer: `[X, Y, Z] :: 1..10`

In Picat's `cp` module, the `::` operator is used to associate a domain with one or more constraint variables. The syntax `Variables :: Domain` correctly assigns the specified integer range to each variable in the list.

What is the fundamental difference between the standard Picat unification operator `=` and the CP constraint equality operator `#=` within a `cp` model?

Answer: The `=` operator immediately attempts to bind a variable, whereas `#=` posts a constraint that must be satisfied in the final solution.

The standard unification operator `=` tries to make two terms identical immediately. If a variable is free, it will be bound. The CP constraint operator `#=`, however, does not perform immediate binding. Instead, it adds a constraint to the solver stating that the expressions on both sides must be equal in any valid solution found by `solve`.

A programmer is building a scheduling model where two tasks, Task A and Task B, cannot overlap. Task A starts at time `S1` and has duration `D1`. Task B starts at `S2` and has duration `D2`. Which of the following constraints correctly models that Task A must finish before Task B starts OR Task B must finish before Task A starts?

Answer: `S1 + D1 #=< S2 #/ S2 + D2 #=< S1`

This is a classic disjunctive scheduling constraint. The condition `S1 + D1 #=< S2` means Task A finishes at or before Task B begins. The condition `S2 + D2 #=< S1` means Task B finishes at or before Task A begins. The disjunction operator `#\/` ensures that at least one of these two conditions must hold true in the final solution, preventing any overlap.

After importing the `cp` module, what is the role of the `indomain/1` predicate?

Answer: It is a non-deterministic predicate that, upon backtracking, assigns the next value from a variable's domain to that variable.

The `indomain(Var)` predicate is a built-in search primitive. When called, it instantiates `Var` to a value from its domain. It is non-deterministic, meaning that if execution backtracks to this point, it will fail the previous assignment and try the next value in the domain until all values have been exhausted. It is a fundamental building block for custom search strategies.