- Dear friends,i bought the book of artificial intelligence and at this moment i am studying algorithms that solves CSP problems.My question is: How the AC-3 algorithm solves N-Queen problems? The arc consistency algorithm don´t prune any domain values of the variables. In the end, the algorithm acts just like the regular backtracking algorithm. Am i missing some detail?My second attempt was to prune values from the second variable (Xj) of the constraint whenever the assigned value of the first variable ()Xi don´t satisfies the constraint.At the end of the loop, i put back the values prunned from the second variable (Xj). But that didn´t work either.If someone can help me i would be really grateful!
- Hi,In initial state, when the board is empty, AC-3 doesn't change any domain because there is no arc inconsistence; but if try the same in other state it will help.For example: suposse that you have 3 vars, one per column; and the domains of that vars are [0,1,2,3] (the row of that queen); the state with only one queen on the top left corner is:v1 v2 v3+---+---+---+0 | Q | | |+---+---+---+1 | | | |+---+---+---+2 | | | |+---+---+---+3 | | | |+---+---+---+If you apply **forward checking** in that state it will prune v2 and v3 domains in this way (marked with X):v1 v2 v3+---+---+---+0 | Q | X| X |+---+---+---+1 | X | X | |+---+---+---+2 | X | | X |+---+---+---+3 | X | | |+---+---+---+Hope I help you..regards2013/11/4 <julioheitor@...>Dear friends,i bought the book of artificial intelligence and at this moment i am studying algorithms that solves CSP problems.My question is: How the AC-3 algorithm solves N-Queen problems? The arc consistency algorithm don´t prune any domain values of the variables. In the end, the algorithm acts just like the regular backtracking algorithm. Am i missing some detail?My second attempt was to prune values from the second variable (Xj) of the constraint whenever the assigned value of the first variable ()Xi don´t satisfies the constraint.At the end of the loop, i put back the values prunned from the second variable (Xj). But that didn´t work either.If someone can help me i would be really grateful!
Ariel,

thanks for your awnser!

But, you are assuming that the column values are fixed for every var, right?

In this case there is no difference between forward checking and AC-3. :(

---In aima-talk@yahoogroups.com, <arielrossanigo@...> wrote:

Hi,In initial state, when the board is empty, AC-3 doesn't change any domain because there is no arc inconsistence; but if try the same in other state it will help.For example: suposse that you have 3 vars, one per column; and the domains of that vars are [0,1,2,3] (the row of that queen); the state with only one queen on the top left corner is:v1 v2 v3+---+---+---+0 | Q | | |+---+---+---+1 | | | |+---+---+---+2 | | | |+---+---+---+3 | | | |+---+---+---+If you apply **forward checking** in that state it will prune v2 and v3 domains in this way (marked with X):v1 v2 v3+---+---+---+0 | Q | X| X |+---+---+---+1 | X | X | |+---+---+---+2 | X | | X |+---+---+---+3 | X | | |+---+---+---+Hope I help you..regards2013/11/4 <julioheitor@...>Dear friends,i bought the book of artificial intelligence and at this moment i am studying algorithms that solves CSP problems.My question is: How the AC-3 algorithm solves N-Queen problems? The arc consistency algorithm don´t prune any domain values of the variables. In the end, the algorithm acts just like the regular backtracking algorithm. Am i missing some detail?My second attempt was to prune values from the second variable (Xj) of the constraint whenever the assigned value of the first variable ()Xi don´t satisfies the constraint.At the end of the loop, i put back the values prunned from the second variable (Xj). But that didn´t work either.If someone can help me i would be really grateful!- Hi Julio, what did you mean with fixed?I'm assuming this:* Every var represents a queen on one column.* For each var, the domain is the number of the row where the queen is. In the example each var have [0, 1, 2, 3] as its domain.* For each pair of vars I've a binary restriction that is violated if this 2 vars are attacked each other.In the example Forward checking makes less work than AC-3:Forward checkink:v1 v2 v3+---+---+---+0 | Q | X| X |+---+---+---+1 | X | X | |+---+---+---+2 | X | | X |+---+---+---+3 | X | | |+---+---+---+AC-3:v1 v2 v3+---+---+---+0 | Q | X| X |+---+---+---+1 | X | X | |+---+---+---+2 | X | ** | X |+---+---+---+3 | X | | ** |+---+---+---+2013/11/5 <julioheitor@...>
Ariel,

thanks for your awnser!

But, you are assuming that the column values are fixed for every var, right?

In this case there is no difference between forward checking and AC-3. :(

---In aima-talk@yahoogroups.com, <arielrossanigo@...> wrote:Hi,In initial state, when the board is empty, AC-3 doesn't change any domain because there is no arc inconsistence; but if try the same in other state it will help.For example: suposse that you have 3 vars, one per column; and the domains of that vars are [0,1,2,3] (the row of that queen); the state with only one queen on the top left corner is:v1 v2 v3+---+---+---+0 | Q | | |+---+---+---+1 | | | |+---+---+---+2 | | | |+---+---+---+3 | | | |+---+---+---+If you apply **forward checking** in that state it will prune v2 and v3 domains in this way (marked with X):v1 v2 v3+---+---+---+0 | Q | X| X |+---+---+---+1 | X | X | |+---+---+---+2 | X | | X |+---+---+---+3 | X | | |+---+---+---+Hope I help you..regards2013/11/4 <julioheitor@...>Dear friends,If someone can help me i would be really grateful! Hi Ariel,

it worked when i used the AC-3 only after the forward checking prunned some values from the domain of the neighbors variables.

Thanks for your awnser!