Picat Constraint Programming with CP Questions and Answers — Questions and Answers
Question 1: When modeling a constraint satisfaction problem in Picat using the `cp` module, what is the primary purpose of the `solve/1` predicate?
- To declare the domains of the constraint variables.
- To post the arithmetic and global constraints to the solver.
- To initiate the search process for finding a valid assignment of values to the variables. (Correct answer)
- To verify if a manually assigned set of values satisfies all constraints.
Correct 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.
Question 2: 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?
- `element/3`
- `sum/1`
- `global_cardinality/2`
- `alldifferent/1` (Correct answer)
Correct 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.
Question 3: 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?
- `[X, Y, Z] :: 1..10` (Correct answer)
- `[X, Y, Z] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}`
- `domain([X, Y, Z], 1, 10)`
- `foreach(V in [X,Y,Z]) V in 1..10 end`
Correct 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.
Question 4: What is the fundamental difference between the standard Picat unification operator `=` and the CP constraint equality operator `#=` within a `cp` model?
- The `#=` operator works only with integers, while `=` works with any data type.
- The `=` operator immediately attempts to bind a variable, whereas `#=` posts a constraint that must be satisfied in the final solution. (Correct answer)
- There is no difference; they are interchangeable within a `cp` model.
- The `#=` operator is used for destructive assignment, similar to `:=`, while `=` is for logical unification.
Correct 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`.
Question 5: 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?
- `S1 + D1 #!= S2`
- `S1 + D1 #< S2 + D2`
- `S1 + D1 #=< S2 #/ S2 + D2 #=< S1` (Correct answer)
- `alldifferent([S1, D1, S2, D2])`
Correct 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.
Question 6: After importing the `cp` module, what is the role of the `indomain/1` predicate?
- It checks if a specific value is within the initial domain of a variable.
- It is a search strategy option used within the `solve/2` predicate.
- It is a non-deterministic predicate that, upon backtracking, assigns the next value from a variable's domain to that variable. (Correct answer)
- It constrains a variable to have a domain that is a subset of another variable's domain.
Correct 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.
Picat Constraint Programming with CP Questions and Answers
When modeling a constraint satisfaction problem in Picat using the `cp` module, what is the primary purpose of the `solve/1` predicate?