Tuesday, May 15, 2012

The n-Queens Problem












import java.util.*;       //to import Scanner class for take the value from user of the chess board

public class quen{
int[] x=new int[16];      //allocate a location for array storage



    public void Nquens(int r, int n){
        for(int c=0;c<n;c++){
            if (canPlace(r,c)){
                x[r] =c;
                if(r==n-1){  //it's say successfully filled
                    print(x,n);
                    board(x,n);
                    break;
                }
            else Nquens(r+1,n); //call or move 1st one queen to up box
             }
        }
    }

    boolean canPlace(int r,int t){   // to check can place or not
        for(int i=0;i<r;i++){
        if (x[i]==t||Math.abs(i-r)==Math.abs(x[i]-t)) //to check if any queen take place in vertical or horizontal line
        return false;
        }
        return true;
    }
       
       
       
    public void print(int[] y,int n){     //print the possible way
    System.out.println();
    System.out.println("another posible way");
    System.out.println();
   
        for (int i=0;i<n;i++){//n or y.length
            System.out.print(y[i]+"|");
            }
            System.out.println();
            System.out.println("board");
        }
       
       
       
    public void board(int[] y,int n){  //command for print chess board
        for(int i=0;i<n;i++){
        System.out.println();
            for(int j=0;j<n;j++){
                if(j==y[i]){
                System.out.print("Q"+"|");}
                else{
            System.out.print("*"+"|");}
            }
            System.out.println();
            for(int k=0;k<2*n;k++){
            System.out.print("-");}
            }
        }
       
       
       
    public static void main(String arg[]){   //main method head of the program 
    Scanner p=new Scanner(System.in);   // to take the input from outside
    System.out.println("enter your board length");
    System.out.println();
    int r=p.nextInt();    //to assign the value to r that take from outside
    System.out.println("your possible ways are");
        quen x=new quen(); //to create a new instance
        x.Nquens(0,r); //call the method  
    }
}



 Result for above coding



enter your board length
4

your possible ways are
Nquens          (0,4)
canplace        (0,0)
        yes     x[0]=0

Nquens          (1,4)
canplace        (1,0)
0==0    1==0
              no
canplace        (1,1)
0==1    1==1
                no
canplace        (1,2)
0==2    1==2
        yes     x[1]=2

Nquens          (2,4)
canplace        (2,0)
0==0    2==0
                no
canplace        (2,1)
0==1    2==1
2==1    1==1
                no
canplace        (2,2)
0==2    2==2
                no
canplace        (2,3)
0==3    2==3
2==3    1==1
                no
                no
canplace        (1,3)
0==3    1==3
        yes     x[1]=3

Nquens          (2,4)
canplace        (2,0)
0==0    2==0
                no
canplace        (2,1)
0==1    2==1
3==1    1==2
        yes     x[2]=1

Nquens          (3,4)
canplace        (3,0)
0==0    3==0
                no
canplace        (3,1)
0==1    3==1
3==1    2==2
                no
canplace        (3,2)
0==2    3==2
3==2    2==1
1==2    1==1
                no
canplace        (3,3)
0==3    3==3
                no
                no
canplace        (2,2)
0==2    2==2
                no
canplace        (2,3)
0==3    2==3
3==3    1==0
                no
                no
                no
canplace        (0,1)
        yes     x[0]=1

Nquens          (1,4)
canplace        (1,0)
1==0    1==1
                no
canplace        (1,1)
1==1    1==0
                no
canplace        (1,2)
1==2    1==1
                no
canplace        (1,3)
1==3    1==2
        yes     x[1]=3

Nquens          (2,4)
canplace        (2,0)
1==0    2==1
3==0    1==3
        yes     x[2]=0

Nquens          (3,4)
canplace        (3,0)
1==0    3==1
3==0    2==3
0==0    1==0
                no
canplace        (3,1)
1==1    3==0
                no
canplace        (3,2)
1==2    3==1
3==2    2==1
0==2    1==2
        yes     x[3]=2


 posible way
1|3|0|2|
board

*|Q|*|*|
--------
*|*|*|Q|
--------
Q|*|*|*|
--------
*|*|Q|*|
--------                no
canplace        (3,3)
1==3    3==2
3==3    2==0
                no
                no
canplace        (2,1)
1==1    2==0
                no
canplace        (2,2)
1==2    2==1
3==2    1==1
                no
canplace        (2,3)
1==3    2==2
                no
                no
                no
canplace        (0,2)
        yes     x[0]=2

Nquens          (1,4)
canplace        (1,0)
2==0    1==2
        yes     x[1]=0

Nquens          (2,4)
canplace        (2,0)
2==0    2==2
                no
canplace        (2,1)
2==1    2==1
0==1    1==1
                no
canplace        (2,2)
2==2    2==0
                no
canplace        (2,3)
2==3    2==1
0==3    1==3
        yes     x[2]=3

Nquens          (3,4)
canplace        (3,0)
2==0    3==2
0==0    2==0
                no
canplace        (3,1)
2==1    3==1
0==1    2==1
3==1    1==2
        yes     x[3]=1


 posible way
2|0|3|1|
board

*|*|Q|*|
--------
Q|*|*|*|
--------
*|*|*|Q|
--------
*|Q|*|*|
--------                no
canplace        (3,2)
2==2    3==0
                no
canplace        (3,3)
2==3    3==1
0==3    2==3
3==3    1==0
                no
                no
                no
canplace        (1,1)
2==1    1==1
                no
canplace        (1,2)
2==2    1==0
                no
canplace        (1,3)
2==3    1==1
                no
                no
canplace        (0,3)
        yes     x[0]=3

Nquens          (1,4)
canplace        (1,0)
3==0    1==3
        yes     x[1]=0

Nquens          (2,4)
canplace        (2,0)
3==0    2==3
0==0    1==0
                no
canplace        (2,1)
3==1    2==2
                no
canplace        (2,2)
3==2    2==1
0==2    1==2
        yes     x[2]=2

Nquens          (3,4)
canplace        (3,0)
3==0    3==3
                no
canplace        (3,1)
3==1    3==2
0==1    2==1
2==1    1==1
                no
canplace        (3,2)
3==2    3==1
0==2    2==2
                no
canplace        (3,3)
3==3    3==0
                no
                no
canplace        (2,3)
3==3    2==0
                no
                no
canplace        (1,1)
3==1    1==2
        yes     x[1]=1

Nquens          (2,4)
canplace        (2,0)
3==0    2==3
1==0    1==1
                no
canplace        (2,1)
3==1    2==2
                no
canplace        (2,2)
3==2    2==1
1==2    1==1
                no
canplace        (2,3)
3==3    2==0
                no
                no
canplace        (1,2)
3==2    1==1
                no
canplace        (1,3)
3==3    1==0
                no
                no