Arc-Consistency (AC3) and one Challenge?

Question

In Applying Arc-Consistency (AC3) algorithms on one Constraint Satisfaction Problem, if the domain of one variable is empty, what is the next step?

1) halt.

2) do backtrack.

3) start from another initial state.

4) it depends on that we are in which step.

Solution (4). I think (1) is true because it means we cannot find any consistent assignment and halt. anyone can describe why (4) is true?

Answer 1

If the domain of a variable shrink until it is empty, then it means that the constraint problem has no solutions. Hence the algorithm should halt in the failure state. Your solution is exactly wrong. Considering we only remove values from domains when they can never be part of a solution, an empty domain means no solution possible at all. So back out of that branch or halt and start from other branches.