## Using AC-3 to solve N-Quenn problems

Expand Messages
• 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
Message 1 of 5 , Nov 4, 2013
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
Message 2 of 5 , Nov 4, 2013
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 |    |    |
+---+---+---+

regards

2013/11/4

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
Message 3 of 5 , Nov 5, 2013

Ariel,

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 |    |    |
+---+---+---+

regards

2013/11/4

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
Message 4 of 5 , Nov 5, 2013
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

Ariel,

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 |    |    |
+---+---+---+

regards

2013/11/4

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 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
Message 5 of 5 , Dec 13, 2013

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.