forked from hongtaocai/code_interview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathNQueens.cpp
More file actions
52 lines (49 loc) · 1.51 KB
/
NQueens.cpp
File metadata and controls
52 lines (49 loc) · 1.51 KB
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
class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
vector<vector<string> > solutions;
vector<string> board(n);
for(int i=0;i<n;++i) {
for(int j=0;j<n;++j) {
board[i] = board[i] + ".";
}
}
solveNQueensOnRow(n, 0, solutions, board);
return solutions;
}
void solveNQueensOnRow(int n, int row, vector<vector<string> >& solutions, vector<string>& board) {
if(row == n) {
vector<string> sol(board.begin(), board.end());
solutions.push_back(sol);
return;
}
for(int i=0;i<n;i++) {
board[row][i] = 'Q';
if(checkVertical(n, row, i, board) && checkDiagnal(n, row, i, board)) {
solveNQueensOnRow(n, row+1, solutions, board);
}
board[row][i] = '.';
}
}
bool checkVertical(int n, int row, int col, const vector<string>& board) {
for(int i=0;i<row;i++) {
if(board[i][col]=='Q') {
return false;
}
}
return true;
}
bool checkDiagnal(int n, int row, int col, const vector<string>& board) {
for(int i=0;i<row;i++) {
int j = row + col -i;
if(j>=0 && j<n && board[i][j] == 'Q') {
return false;
}
j = i - row + col;
if(j>=0 && j<n && board[i][j] == 'Q') {
return false;
}
}
return true;
}
};