Picat Constraint Programming with CP 4 — Questions and Answers
Question 1: In Picat CP, what does `fd_dom(Var, Dom)` return?
- The number of values in Var's domain
- The domain of Var as a list of values or ranges (Correct answer)
- The constraint set associated with Var
- A boolean indicating whether Var is instantiated
Correct answer: The domain of Var as a list of values or ranges
`fd_dom(Var, Dom)` unifies Dom with a representation of all remaining values in Var's finite domain.
Question 2: Which constraint ensures that the values of variables in a list form a permutation of 1..N in Picat CP?
- permutation(List)
- all_different(List) with domain 1..N (Correct answer)
- assignment(List, N)
- sequence(List, 1, N)
Correct answer: all_different(List) with domain 1..N
Combining `all_different(List)` with each variable's domain set to `1..N` exactly models a permutation constraint.
Question 3: What happens if you post two contradictory constraints, such as `X #= 3` and `X #= 5`, on the same variable in Picat CP?
- The second constraint silently overwrites the first
- A runtime error is raised immediately
- The predicate fails, triggering backtracking (Correct answer)
- Both constraints are stored and checked only at solve time
Correct answer: The predicate fails, triggering backtracking
Constraint propagation detects the empty domain immediately and causes the current goal to fail, which triggers backtracking in the search.
Question 4: In Picat's CP module, the `circuit/1` global constraint is used to model which type of problem?
- Spanning tree construction on a weighted graph
- Hamiltonian cycle over a set of successor variables (Correct answer)
- Shortest-path routing between nodes
- Flow conservation in directed networks
Correct answer: Hamiltonian cycle over a set of successor variables
`circuit(Succ)` constrains the array Succ so that the successor relation forms a single Hamiltonian cycle visiting every node exactly once.
Question 5: Which predicate tests whether a CP variable is already instantiated (ground) in Picat?
- fd_ground(Var)
- ground(Var) (Correct answer)
- instantiated(Var)
- is_fixed(Var)
Correct answer: ground(Var)
`ground(Var)` succeeds if Var is fully instantiated and contains no unbound logical variables.
Question 6: In Picat CP, what does the `max_regret` variable-selection heuristic do?
- Chooses the variable whose two best values differ most, maximizing the cost of wrong choice (Correct answer)
- Selects the variable with the largest domain to delay failure
- Picks the variable with the highest constraint density
- Chooses the variable whose domain maximum is smallest
Correct answer: Chooses the variable whose two best values differ most, maximizing the cost of wrong choice
`max_regret` selects the variable where the difference between the best and second-best domain values is greatest, focusing on high-stakes decisions.
Question 7: What is the role of `scalar_product/4` in Picat's CP module?
- Computes a dot product of two lists and constrains it relative to a bound
- Creates auxiliary variables for each coefficient-variable pair
- Enforces that all coefficients in a list are distinct
- Models a linear constraint between a coefficient vector and variable vector (Correct answer)
Correct answer: Models a linear constraint between a coefficient vector and variable vector
`scalar_product(Coeffs, Vars, Rel, Bound)` posts the linear constraint Coeffs · Vars Rel Bound using the specified relational operator.
Picat Constraint Programming with CP 4
In Picat CP, what does `fd_dom(Var, Dom)` return?