N-Queen Hard -TLE

#1

Question link :https://hack.codingblocks.com/practice/p/406/909
My solution : https://ide.codingblocks.com/#/s/15909
I am using bitset approach to solve this problem. But still I am getting TLE in some test cases.
Kindly suggest me any efficient approach if any.

#2

yes Happy To help Any Time
use this way out

#include
using namespace std;

bool isSafe(int **board,int i,int col,int N){

int x,y;
//Case 1 : Straight left
x=i;y=col;
while(y>=0){
y–;
if(board[x][y]==1)
return false;
}
//Case 2 : Up Left
x=i; y = col;
while(x>0&&y>0){
x–;
y–;
if(board[x][y]==1)
return false;
}

//Case 3 : Up Right
x=i; y = col;
while(x<N-1&&y>0){
x++;
y–;
if(board[x][y]==1)
return false;
}
//Else true in all cases
return true;
}

int countWays(int **board,int col,int n)
{

if(col>=n){
    return 1;
}

int i;
int count =0;
for(i=0;i<n;i++){

//Check if the given position is safe to place the queen , the place the queen ,check for next ! :D
if(isSafe(board,i,col,n)){
    board[i][col]=1;//Place the Queen
    count += countWays(board,col+1,n);
    board[i][col]=0; //Backtrack
    }
}
return count;

}

int main(){
int n,i,j;
cin>>n;

int *board = new int[n];

for(i=0;i<n;i++)
board[i] = new int[n];

for(i=0;i<n;i++)
for(j=0;j<n;j++)
board[i][j]=0;

cout<<“The No of ways “<<n<<” queens can be placed on a “<<n<<” X “<<n<<” chessboard is :”<<endl<<countWays(board,0,n);

return 0;
}

#3

Hi Shrey ! , actually this approach will work only for n<=11 because of time complexity of your code
T(n)=n*T(n-1)+k
So if you want to submit this code then you have to precompute answers for n>11 and use it like this
https://ide.codingblocks.com/#/s/16135