Question

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.
Which of the following are true about this algorithm?
a) If after a run of arc consistency during the backtracking searchwe end up with the filtered domains of allof the not yetassigned variables being empty, this means the CSP has nosolution.
b) If after a run of arc consistency during the backtracking searchwe end up with the filtered domain of oneof the not yetassigned variables being empty, this means the CSP has nosolution.
c) None of the above.

Answer 1

We are given a CSP with only binary can concentrate assume we run backtrackingSearch with ARC