Important-DSA-Questions-With-Solution/N-Queen at main · AnamikaSaini08/Important-DSA-Questions-With-Solution · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution{
public:

    bool isSafe(vector<vector<int>>&v, int i, int j , int n)
    {
       for(int k=i-1; k>=0; k--){
       if(v[k][j]==1)return false;
   }
   int k,l;
   for(k=i-1,l=j-1; k>=0 && l>=0; k--,l--) {
       if(v[k][l]==1)return false;
   }
   for(k=i-1,l=j+1; k>=0 && l<n; k--,l++){
       if(v[k][l]==1)return false;
   }
   return true;
    }
    bool solve(vector<vector<int>>&sol , int row , int n , vector<vector<int>>&ans)
    {
        if(row >= n){
            vector<int>temp;
            for(int i=0 ; i<n ; i++)
                for(int j=0 ; j<n ; j++)
                    if(sol[i][j])
                        temp.push_back(j+1);

            ans.push_back(temp);
            return true;
        }

        for(int col = 0; col<n ; col++)
        {
            if(isSafe(sol , row , col , n))
            {
                sol[row][col] = 1;
                solve(sol , row+1, n , ans);
                sol[row][col] = 0;
            }
        }
        return false;
    }
    vector<vector<int>> nQueen(int n) {
        // code here'
        vector<vector<int>>sol( n , vector<int> (n, 0));
        vector<vector<int>>ans;

        solve(sol , 0 , n , ans);
        return ans;
    }
};