How to avoid time limit exceeded??
import java.util.Scanner;
public class Main {
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
boolean b[][]=new boolean[n][n];
QueenCombination2D(b,0,n,0,0,"");
System.out.println(count);
}
static int count=0;
public static void QueenCombination2D(boolean a[][],int qpsf,int tq,int row,int col,String ans){
if(qpsf==tq){
count++;
//System.out.println(ans);
return;
}
if(col>=a[0].length){
QueenCombination2D(a,qpsf,tq,row+1,0,ans);
return;
}
if(row>=a.length)
return;
if(isSafe(a,row,col)){
a[row][col]=true;
QueenCombination2D(a,qpsf+1,tq,row,col+1,ans+"Queen"+qpsf+" ["+row+","+col+"] ");
//In case of NQueen problem
//QueenCombination2D(a,qpsf+1,tq,row+1,0,ans+"Queen"+qpsf+" ["+row+","+col+"] ");
a[row][col]=false;
}
QueenCombination2D(a,qpsf,tq,row,col+1,ans);
}
public static boolean isSafe(boolean b[][],int row,int col){
//vertically Upward
int r=row-1;
int c=col;
while(r>=0){
if(b[r][c])
return false;
r--;
}
//horizontally Left
r=row;
c=col-1;
while(c>=0){
if(b[r][c])
return false;
c--;
}
//diagonally Right
r=row-1;
c=col+1;
while(r>=0 && c<b[r].length){
if(b[r][c])
return false;
r--;
c++;
}
//diagonally Left
r=row-1;
c=col-1;
while(r>=0 && c>=0){
if(b[r][c])
return false;
r--;
c--;
}
return true;
}
}