N-Queens and Map Coloring (Coursera Discrete Optimization Course)

• Place 8 Queens on a 8*8 board such that none of them attack each other.
• Backtrack: Use constraints to reduce search space.
• Map Coloring: Every 2D map can be colored with 4 colors (upper bound: dimension+1)
• Domain Store is the search space and independent constraints interact with it and if they are feasible, keep reducing the domain store.
• Propagation Engine: Iterative algorithm, bring constraints one by one and if feasible remove values from domain store one by one.
• Decision Variable: A model to associate a part of problem in the form of variable that we can check one by one and solve problem. The constraints will be on this decision variable.

N-Queen Problem ( Call by nqueen(1) )

 public void nqueen(int r,int n,int x[]){
     if(r==n+1) print("Found"+x);
     else{
      boolean legal;
      for(int j=1;j<=n;j++){
       legal=true;
       for(int i=1;i<=r-1;i++)
        if(x[i-1]==j||x[i-1]==j+r-i||x[i-1]==j-r+i) legal=false;
       if(legal){
        x[r-1]=j;
        nqueen(r+1,n,x);
       }
      }
     }
    }