AC-3 Algorithms on CSP problem, What is happened when enocunter to an empty domain variable? Suppose We Applying Arc-Consistency (AC3) algorithms on one Constraint Satisfaction Problem, if domain of one variable be empty, what is the next step of this algorithm?



According to This Link and to Wikipedia's description of AC3: once one domain is empty, the algorithm stops, indicating there is no solution to the CSP.

This book says: if one domain of the non assigned variables becomes empty then backtracks to....



My challenge is about the behavior of this algorithms, i.e, in which
phase (when) AC-3 stops, and when it's select Backtrack.


  Update: Anyone could describe the behaviors of AC-3 on empty domain in
  each phase?




References: This question asked 5 month ago on SO but I think the answer is wrong, because I add some references that shows other things.
You've misunderstood the book.  It's not describing the AC-3 algorithm; it's describing some other algorithm.  The book is describing an algorithm that combines both guess-and-backtrack together with arc consistency.  The AC-3 algorithm doesn't do any guess-and-backtrack; it uses only arc consistency checks.

Thus, AC-3 does terminate if there is some variable whose domain set becomes empty; in this case, AC-3 declares the constraint system unsatisfiable (inconsistent).  This is the correct thing to do, in the context of the AC-3 algorithm.

Of course, if you're talking about some totally different algorithm (like the book is), that other algorithm might do something totally different.  No great surprise there.

I don't see anything wrong with the answer to the Stack Overflow question you link to.