N-Queens
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.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."], ["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
这题和Sudoku Solver是一个套路，回溯法尝试所有可能性，将可行解的保存起来。可以对比着看。
由于这里路径尝试本质上是有序的，即1~9逐个尝试，因此无需额外设置状态位记录已经尝试过的方向。
我们先用vector<int>来存放可行解，下标代表行号，元素代表列号。
因此上图中Solution 1用vector<int>表示就是[1,3,0,2]
解题流程就是在下一行中尝试列数(0~n-1)，如果可行则递归下去，如果不可行则弹出继续尝试下一列。
最后将vector<vector<int> > 转为vector<vector<string> >即可。
class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
return convert(solve(n), n);
}
vector<vector<int> > solve(int n)
{
vector<vector<int> > ret;
vector<int> cur;
Helper(ret, cur, , n);
return ret;
}
void Helper(vector<vector<int> >& ret, vector<int> cur, int pos, int n)
{
if(pos == n)
ret.push_back(cur);
else
{
for(int i = ; i < n; i ++)
{
cur.push_back(i);
if(check(cur))
Helper(ret, cur, pos+, n);
cur.pop_back();
}
}
}
bool check(vector<int> cur)
{
int size = cur.size();
int loc = cur[size-];
for(int i = ; i < size-; i ++)
{
if(cur[i] == loc)
return false;
else if(abs(cur[i]-loc) == abs(i-size+))
return false;
}
return true;
}
vector<vector<string> > convert(vector<vector<int> > ret, int n)
{
vector<vector<string> > retStr;
for(int i = ; i < ret.size(); i ++)
{
vector<string> curStr;
for(int j = ; j < n; j ++)
{
string loc(n, '.');
loc[ret[i][j]] = 'Q';
curStr.push_back(loc);
}
retStr.push_back(curStr);
}
return retStr;
}
};