Problem
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
Example
Input: 4 Output: [ [".Q…", // Solution 1 “…Q”, “Q…”, “…Q.”], ["…Q.", // Solution 2 “Q…”, “…Q”, “.Q…”] ] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
Solution
class Solution {
public:
vector
<bool> col_used
;
vector
<bool> diag_used
;
vector
<bool> udiag_used
;
vector
<vector
<string
>> ret
;
vector
<string
> cur_conf
;
vector
<vector
<string
>> solveNQueens(int n
) {
col_used
.resize(n
,false);
diag_used
.resize(2 * n
- 1 ,false);
udiag_used
.resize(2 * n
-1 ,false);
dfs(0,n
);
return ret
;
}
void dfs(int row
,int n
)
{
if(row
== n
)
{
ret
.push_back(cur_conf
);
return;
}
string
line_conf(n
,'.');
for(int i
= 0;i
<n
;++i
)
{
if(!col_used
[i
] && !diag_used
[row
+ i
] && !udiag_used
[i
- row
+ n
-1])
{
col_used
[i
] = diag_used
[row
+ i
] = udiag_used
[i
- row
+ n
-1] = true;
line_conf
[i
] = 'Q';
cur_conf
.push_back(line_conf
);
dfs(row
+ 1,n
);
cur_conf
.pop_back();
line_conf
[i
] = '.';
col_used
[i
] = diag_used
[row
+ i
] = udiag_used
[i
- row
+ n
-1] = false;
}
}
}
};
