Loading ...
Sorry, an error occurred while loading the content.

Using AC-3 to solve N-Quenn problems

Expand Messages
  • juliohsn
    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
    • 0 Attachment
      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 Rossanigo
      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
      • 0 Attachment
        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..

        regards



        2013/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!


      • juliohsn
        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
        • 0 Attachment

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

          regards



          2013/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 Rossanigo
          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
          • 0 Attachment
            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..

            regards



            2013/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!


          • juliohsn
            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
            • 0 Attachment

              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!

            Your message has been successfully submitted and would be delivered to recipients shortly.