Leetcode/leetcode51.cpp at main · ksaini-web/Leetcode · 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
public:

bool issafe(vector<string>&board,int row,int col,int n){

    //horizontal
    for(int j=0;j<n;j++){
        if(board[row][j]=='Q'){
            return false;
        }
    }
    //vertical
     for(int i=0;i<n;i++){
        if(board[i][col]=='Q'){
            return false;
        }
    }

    //left digonal

    for(int i=row, j=col; i>=0&&j>=0;i--,j--){

        if(board[i][j]=='Q'){
            return false;
        }
    }

    for(int i=row, j=col;i>=0&&j<n;i--,j++){

         if(board[i][j]=='Q'){
            return false;
        }
    }
return true;
}

  void nQueens(vector<string> &board,int row,int n,vector<vector<string>>&ans){
  //base case

  if(row==n){
    ans.push_back({board});
    return ;
  }

  for(int j=0;j<n;j++){
  if(issafe(board,row,j,n)){
    board[row][j]='Q';
    nQueens(board,row+1,n,ans);
    board[row][j]='.';
  }}

  }


    vector<vector<string>> solveNQueens(int n) {

        vector<string>board(n,string(n,'.'));
        vector<vector<string>>ans;

       nQueens(board,0,n,ans);
        return ans;

    }
};