Question
Variables in these problems may be represented using a hypergraph of their namesake statements. For 10 points each:
[10m] Name these problems that seek to assign values to a set of variables without violating any of the namesake statements. Type inference and circuit-board layout are tasks often modeled using these problems.
ANSWER: constraint satisfaction problems [or CSPs; accept constraint optimization or constrained optimization or constraint programming; accept COs or COPs; prompt on constraint problems or satisfaction problems]
[10h] Techniques leveraging this property help to prune the search space in complex constraint satisfaction problems. The “node,” “arc,” and “path” forms of this property are used to enforce constraints of varying order.
ANSWER: local consistency [accept more specific answers, such as node consistency, arc consistency, path consistency, or k-consistency]
[10e] While consistency methods use inference to solve CSPs, this class of algorithms is often used to solve CSPs using search. The eight queens problem is a classic example of a problem solved using this class of algorithms, which retraces steps when a dead-end is reached.
ANSWER: backtracking
<DN, Other Science (Computer Science)>
Data
Summary
| Tournament | Edition | Exact Match? | Heard | PPB | Easy % | Medium % | Hard % |
|---|---|---|---|---|---|---|---|
| 2024 Chicago Open | 07/28/2024 | Y | 15 | 7.33 | 27% | 40% | 7% |