- DATA.ML.310
- 4. Adversarial Search and Constraint Satisfaction Problems
- 4.3 Quiz: Constraint satisfaction problems

# Quiz: Constraint satisfaction problems¶

Is the following statement True or False?

If the CSP has no solution, it is guaranteed that enforcement of arc consistency resulted in at least one domain being empty.

Is the following statement True or False?

If the CSP has a solution, then after enforcing arc consistency, you can directly read off the solution from resulting domains.

Is the following statement True or False?

In general, to determine whether the CSP has a solution, enforcing arc consistency alone is not sufficient; backtracking may be required.

We are given a CSP with only binary constraints. Assume we run backtracking search with arc consistency as follows. Initially, when presented with the CSP, one round of arc consistency is enforced. This first round of arc consistency will typically result in variables having pruned domains. Then we start a backtracking search using the pruned domains. In this backtracking search we use filtering through enforcing arc consistency after every assignment in the search.

Is the following statement True or False?

If after a run of arc consistency during the backtracking search we end up with the filtered domains of all of the not yet assigned variables being empty, this means the CSP has no solution.

We are given a CSP with only binary constraints. Assume we run backtracking search with arc consistency as follows. Initially, when presented with the CSP, one round of arc consistency is enforced. This first round of arc consistency will typically result in variables having pruned domains. Then we start a backtracking search using the pruned domains. In this backtracking search we use filtering through enforcing arc consistency after every assignment in the search.

Is the following statement True or False?

If after a run of arc consistency during the backtracking search we end up with the filtered domain of one of the not yet assigned variables being empty, this means the CSP has no solution.

We are given a CSP with only binary constraints. Assume we run backtracking search with arc consistency as follows. Initially, when presented with the CSP, one round of arc consistency is enforced. This first round of arc consistency will typically result in variables having pruned domains. Then we start a backtracking search using the pruned domains. In this backtracking search we use filtering through enforcing arc consistency after every assignment in the search.

Is the following statement True or False?

If after a run of arc consistency during the backtracking search we end up with the filtered domains of all of the not yet assigned variables being empty, this means the search should backtrack because this particular branch in the search tree has no solution.

Is the following statement True or False?

If after a run of arc consistency during the backtracking search we end up with the filtered domain of one of the not yet assigned variables being empty, this means the search should backtrack because this particular branch in the search tree has no solution.

Is the following statement True or False?

If after a run of arc consistency during the backtracking search we end up with the filtered domains of all of the not yet assigned variables each having exactly one value left, this means we have found a solution.

Is the following statement True or False?

If after a run of arc consistency during the backtracking search we end up with the filtered domains of all of the not yet assigned variables each having more than one value left, this means we have found a whole space of solutions and we can just pick any combination of values still left in the domains and that will be a solution.

Is the following statement True or False?

If after a run of arc consistency during the backtracking search we end up with the filtered domains of all of the not yet assigned variables each having more than one value left, this means we can’t know yet whether there is a solution somewhere further down this branch of the tree, and search has to continue down this branch to determine this.

Is the following statement True or False?

Even when using arc consistency, backtracking might be needed to solve a CSP.

Is the following statement True or False?

Even when using forward checking, backtracking might be needed to solve a CSP.

Is the following statement True or False?

Solving a CSP problem means finding the assignment(s) that satisfy all constraints.

Consider the map-coloring problem in the figure above. If there are 3 colors available, how many solutions are there?

Consider the map-coloring problem in the figure above. If there are 4 colors available, how many solutions are there?

Consider the map-coloring problem in the figure above. If there are 2 colors available, how many solutions are there?