Monday, 15 October 2012

N Queen Algorithm

package eight.queen.algorithm;



public class Queen {
 
 private int N = 8; 
 private int chess[][];
 
 
 public Queen(){
  chess = new int[N][N];
  System.out.println(N+" sizes chess table contain "+NQueen(0)+"\n");
 }
 
 public int NQueen(int currentRow){
  
  if(currentRow==N)
   return 1;
  int totalQueenSetting = 0;
  for(int i = 0;i<N;i++){
   if(chess[currentRow][i]==0){ 
    chess[currentRow][i] = 1+currentRow;
    setConsumedSquares(currentRow,i);
    
    totalQueenSetting += NQueen(currentRow+1);
    for(int k = 0; k<N;k++)
     for(int j = 0;j<N;j++)
      if(chess[k][j]==8){
       print();
       System.out.println("\t");
       break;
      }
    chess[currentRow][i] = 0;
    recover(currentRow);
   }
  }
  return totalQueenSetting;
 }
 public void setConsumedSquares(int row,int i){
  for(int j = row+1;j<N;j++){
   if(chess[j][i]==0)
   chess[j][i] = (1+row);
   if(i-(j-row)>=0 && chess[j][i-(j-row)] == 0)
    chess[j][i-(j-row)] = (1+row);
   if(i+(j-row) < N && chess[j][i+(j-row)] == 0)
    chess[j][i+(j-row)] = (1+row);
  }
   
 }
 public void recover(int row){
  for(int i = row;i<N;i++)
   for(int j = 0;j<N;j++)
    if(chess[i][j]==(1+row))
     chess[i][j] = 0;
 }
 public void print(){
  for(int i = 0; i<N;i++)
   for(int j = 0;j<N;j++){
    System.out.print(chess[i][j]+" ");
    if(j == N-1)
     System.out.println("\t");
   }
 }
 public static void main(String[] args){
  Queen test = new Queen();
  
 }
}

No comments:

Post a Comment