The code below is giving TLE. As far as taught, this is the best approach for this question but still giving TLE.
More over, the same code gives score of 66 and 83 when run again.
#include<bits/stdc++.h>
using namespace std;
int getPosition(int n) {
int pos = 0;
while(n) {
pos++;
n >>= 1;
}
return pos-1;
}
void solve(int row_mask, int ld, int rd, int row, int done, int &ans, int n, int board[][100]) {
// base case
if(row_mask == done) {
ans++;
return;
}
int safe = done & (~(row_mask | ld | rd));
// find the solution for all set bits in safe
while(safe) {
int p = safe & (-safe);
int col = getPosition§;
board[row][col] = 1;
safe = safe - p;
// recursive call
solve(row_mask | p, (ld | p) << 1, (rd | p) >> 1, row+1, done, ans, n, board);
// backtrack if not able to place all queens safely
board[row][col] = 0;
}
}
int main() {
int n;
cin >> n;
int board[100][100] = {0};
int ans = 0;
// done is the mask denoting work is finished
int done = (1 << n) - 1;
solve(0, 0, 0, 0, done, ans, n, board);
cout << ans;
return 0;
}
the test cases and constraints are updated.