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.

  • 2
    $\begingroup$ Welcome to CS.SE! 1. You say "some references say". Please edit the question to provide at least one citation for each claim, so we can read what they say for ourselves and see the context. In particular, please try to provide at least one citation for each claim -- ideally, where you can provide a full citation (authors, title, where published) and a link to freely available text, and a pointer to a specific place where that is said, or a quotation with appropriate context. $\endgroup$ – D.W. Jul 22 '16 at 1:38
  • 2
    $\begingroup$ 2. What are your thoughts? What's your reasoning? Why do you think the answer on SO is wrong? I'm not sure what you mean by "I add some references that shows other things" -- I don't see any references in this question, merely a claim that such references exist. It'd help if could edit the question to spell out your reasoning. $\endgroup$ – D.W. Jul 22 '16 at 1:39
  • 2
    $\begingroup$ 3. You claim "This book" says backstrack and start from other points. Where does it say that? Please provide a precise quotation. I don't see it saying that anywhere. 4. Rather than providing just a "this book" and a link to Google Books, please provide a full citation, including title and authors. We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. Thank you! $\endgroup$ – D.W. Jul 22 '16 at 4:47
  • 1
    $\begingroup$ I'm afraid it needs a bit more editing -- re-read my comments. We need you to edit the question to address my point 3 (see above). Also we want a full citation for each claim. Just linking and saying "This link" or "this book" aren't good enough -- we want a question that will remain working even if those links stop working. Also, you should edit to add your thoughts and your reasoning; why do you think "this book" says otherwise? What is your detailed reasoning? Please support your reasoning with quotes from the book. Please take some time to improve your question. Thank you! $\endgroup$ – D.W. Jul 22 '16 at 10:31
  • 2
    $\begingroup$ If you have doubts in the answer of the question on SO, you really should ask it on SO. If you want to ask it here, you need to provide full context so that we, the users on CS.SE, will understand the question. Right now, the question is unclear, in my opinion. By the way, I did not ask the question, nor answer the question on SO. $\endgroup$ – scaaahu Jul 22 '16 at 13:24

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.

| cite | improve this answer | |
  • $\begingroup$ Please see question 3- Part (b) or search backtrack in this file, s3-us-west-2.amazonaws.com/cs188websitecontent/exams/… $\endgroup$ – Michle Niaye Jul 25 '16 at 7:31
  • $\begingroup$ @MichleNiaye, what about it? That exam problem isn't talking about the AC-3 algorithm, either. It explicitly says "You decide to try a new approach..." (i.e., not AC-3; something different). $\endgroup$ – D.W. Jul 25 '16 at 11:26
  • $\begingroup$ Ok, about this exam you are right, Is it possible to talk with you? the question says we run AC-3 on CSP problem, isn't related? $\endgroup$ – Michle Niaye Jul 25 '16 at 11:30

At the very first phase when you give empty domain it is non-conditional failure - it is the same as saying: "I have a function $f(x) = x^2 + 1$, but $x \in {\emptyset}$, find me feasible solutions, which are none.
In the phase when arcs are getting cut you check if the values are consistent between two variables - here arc is either in solution or is inconsistent.
You have the same function as above and points: $x \in \{0, 1\}, y \in \{1, 5\}$. This makes one consistent pair, the second is cut, it will not be in the solution. At this point if there were more constraints you would check the consistency of related variables (You might call it backtrack, because another variable that is related takes part, but here you might find that there are no arc, and it is perfectly fine here). But if $x \in \{23, 45\}$ then you cannot find any good pair, but now it turns out that domains of $x$ is $\emptyset$, so something was inconsistent - with checked constraints you have no feassible points, so it is failure.

The sildes you have provided show that AC-3 is detecting wrong candidate for solution faster than forward checking. The outer scheme is backtracking solver, which at every step assumes one of possible values, assigns it and continues guessing values until it finds solution or contradiction (in such case it goes back to assumption made and changes it to different possible value). Slides show that propagating constraints is superior to propagating values, because it allow faster checking of error.

AC-3 in this context is used as black-box function to determine failure, but the pure algorithm itself does not backtrack - it operates on one given instance - candidate for solution, and it's output serves as indicator to backtracking.

| cite | improve this answer | |
  • $\begingroup$ Sorry Evil, thanks from your well descriptive answer, D.W post and say the AC-3 hasn't backtrack. I think AC-3 on CSP has. would you please clarify it for me? thanks. $\endgroup$ – Michle Niaye Jul 25 '16 at 22:59
  • $\begingroup$ Of course. D.W. Is right, AC-3 does not backtrack, I thought that you call one thing backtrack and I wrote it in the place where I thought that you use this term. In the link I gave you there was backtracking, but it was AC-3 merged with other concepts. D.W. comment about the link you provided (I have not seen it earlier) was accurate. AC-3 does consistency test without backtracking, but of course it might be used with other techniques. But the test option about backtracking was bad choice. I would propose to look at some implementation and look at pure AC-3. $\endgroup$ – Evil Jul 25 '16 at 23:18
  • $\begingroup$ "It explicitly says "You decide to try a new approach..." (i.e., not AC-3; something different)." - I have read the task right now and as D.W. cited and paper says - it is a mixture of consistency check and backtracking, so there was some confusion but I hope it is clearer now as we get into the source. $\endgroup$ – Evil Jul 25 '16 at 23:26
  • $\begingroup$ Please let me to study more and say my idea. but one problem so you means AC-3 on CSP problem again is not using backtracking? Answer with yes or no please? I study more until tomorrow. $\endgroup$ – Michle Niaye Jul 25 '16 at 23:36
  • $\begingroup$ This is very critical for me and studying, please let me know your idea with Yes/No about AC-3 on CSP problem again is not using backtracking? thanks. $\endgroup$ – Michle Niaye Jul 25 '16 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.