forked from GurmanBhullar/hactoberfest-DsAlgo
-
Notifications
You must be signed in to change notification settings - Fork 0
/
NQueens.cpp
121 lines (90 loc) · 2.35 KB
/
NQueens.cpp
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
/*
You are given N, and for a given N x N chessboard, find a way to place N queens such that no queen can attack any other queen on the chess board. A queen can be killed when it lies in the same row, or same column, or the same diagonal of any of the other queens. You have to print all such configurations.
Input Format :
Line 1 : Integer N
Output Format :
One Line for every board configuration.
Every line will have N*N board elements printed row wise and are separated by space
Note : Don't print anything if there isn't any valid configuration.
Constraints :
1<=N<=10
Sample Input 1:
4
Sample Output 1 :
0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0
0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0
*/
#include <vector>
#include<iostream>
using namespace std;
void printboard(vector<vector <int> > qboard){
for(int i=0;i<qboard.size();i++){
for(int j=0;j<qboard[i].size();j++){
cout<<qboard[i][j]<<" ";
}
}
}
bool qdiagcheck(vector<vector <int> > qboard,int r,int c){
int i=0;
int n=qboard.size();
while(r+i<n && c+i<n){
if(qboard[r+i][c+i])
return false;
i++;
}
i=0;
while(r-i>=0 && c+i<n){
if(qboard[r-i][c+i])
return false;
i++;
}
i=0;
while(r+i<n && c-i>=0){
if(qboard[r+i][c-i])
return false;
i++;
}
i=0;
while(r-i>=0 && c-i>=0){
if(qboard[r-i][c-i])
return false;
i++;
}
return true;
}
bool qrccheck(vector<vector <int> > qboard,int r,int c){
//Column-Check
for(int i=0;i<qboard.size();i++){
if(qboard[i][c])
return false;
}
return true;
}
void solve(vector <vector<int> >qboard,int n,int r){
if(n==0){
printboard(qboard);
cout<<endl;
return;
}
for(int i=0;i<qboard.size();i++){
if(qdiagcheck(qboard,r,i) && qrccheck(qboard,r,i)){
qboard[r][i]=1;
solve(qboard,n-1,r+1);
}
qboard[r][i]=0;
}
return;
}
void placeNQueens(int n){
/* Don't write main().
* Don't read input, it is passed as function argument.
* Print output as specified in the question
*/
vector <vector<int> >qboard(n,vector<int>(n,0));
solve(qboard,n,0);
}
int main(){
int n;
cin >> n ;
placeNQueens(n);
}