The solution to this problem is backtracking. Notice, we can use an array to represent the trial result(because every row must has and only has one queen.Each cell in the array represent the choice of each row.When we found a solution to putting queens, we can transform the array from one dimension to two dimension(“…..Q…”).) Most important, we could use
(abs(i-putQueenI)==abs(queenStatus[i]-putQueenJ))
to judge if the new putting location is suitable for diagonal(the queens it put before). Here, i means the row it put before,queenStatus[i] means the place it put on in that row. putQueenI and putQueenJ are the new putting location.
/*
一开始写了深度优先和广度优先的版本都不成功（深度的超时，广度的超内存）。发觉自己的算法没有优化，好多地方都耗时间，优化后用一维数组记录就可以了。（一开始用二维数组后面发觉判断只需要一维就可以了）
*/
//维持一个一维数组，而不是二维的，最后需要输入答案的时候才转换成二维的输入
class Solution
{
private:
vector<vector<string> >result;
//转换成二维数组的函数
vector<string> transformToMatrix(vector<int> queenStatus,int n)
{
vector<string> matrix(n,string(n,'.'));
for (int i=0; i<n; i++)
{
matrix[i][queenStatus[i]]='Q';
}
return matrix;
}
//检查是否能在那个位置放置皇后
bool check(vector<int> &queenStatus,int putQueenI,int putQueenJ,int n)
{
for (int i=0; i<putQueenI; i++)
{
if (queenStatus[i]==putQueenJ) return false; //检查纵向
if (abs(i-putQueenI)==abs(queenStatus[i]-putQueenJ)) return false;//检查斜线
}
return true;
}
//回溯使用的函数
void putQueen(int index,vector<int> &queenStatus,int n)
{
if (index>=n)
{
result.push_back(transformToMatrix(queenStatus,n));
return;
}
for (int j=0; j<n; j++)
{
if (check(queenStatus,index,j,n))
{
queenStatus[index]=j;
putQueen(index+1,queenStatus,n);
queenStatus[index]=-1;
}
}
}
public:
vector<vector<string> > solveNQueens(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
result.clear();
vector<int> queenStatus(n,-1);
putQueen(0,queenStatus,n);
return result;
}
};
Actually, we can use the same solution of N-Queens to solve this problem.Instead of recording all the solution of putting queens, we just add 1 to a counter when we found a solution of putting queens on the chessboard.
class Solution {
private:
int result;
//检查是否能在那个位置放置皇后
bool check(vector<int> &queenStatus,int putQueenI,int putQueenJ,int n)
{
for (int i=0; i<putQueenI; i++)
{
if (queenStatus[i]==putQueenJ) return false; //检查纵向
if (abs(i-putQueenI)==abs(queenStatus[i]-putQueenJ)) return false;//检查斜线
}
return true;
}
//回溯使用的函数
void putQueen(int index,vector<int> &queenStatus,int n)
{
if (index>=n)
{
result++;
return;
}
for (int j=0; j<n; j++)
{
if (check(queenStatus,index,j,n))
{
queenStatus[index]=j;
putQueen(index+1,queenStatus,n);
queenStatus[index]=-1;
}
}
}
public:
int totalNQueens(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
result=0;
vector<int> queenStatus(n,-1);
putQueen(0,queenStatus,n);
return result;
}
};
The performance of this method is very low.(The large data Test)
Then I find another solution on the Internet which is much more faster. The main idea of the second solution is that we mark down the location which could not put queens on in the next row,which means that when we put the queen on that row, we do not need to check the row before to see if there is a queen can eat this queen. And we can use the bit operation to make it faster.(Obviously, this method can also be use to solve N-Queen problem.But in here, I just gave the source code to solve N-QueensII problem)
class Solution {
private:
long upperlimit;
long sum;
void compute(long row,long ld,long rd)
{
if (row!=upperlimit)
{
long pos=upperlimit & ~(row | ld | rd);
while (pos!=0)
{
long p=pos & -pos;
pos=pos-p;
compute(row + p, (ld + p)<< 1, (rd + p)>> 1);
}
}
else
{
sum++;
}
}
public:
int totalNQueens(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
sum=0;
upperlimit=1;
upperlimit=(upperlimit<<n)-1;
compute(0,0,0);
return sum;
}
};
row is the variant indicate the vertical occupation, ld is the left diagonal occupation, rd is the right diagonal occupation.
upperlimit is indicate the final status, for example 1111 (4*4 matrix, four queens) ,111 (3*3 matrix, 3 queens)
row | ld | rd are the occupation in that row.(vertical, left diagonal line and right diagonal line) ~(row | ld | rd) represent the position which can put queens (i.e 10011 means position 1, 4, 5 can put queens).Because the length of type long may be larger than the numbers of rows in the chessboard.(The type long may have more than 10 bits, while the chessboard may be only 5*5)Thus, we need to upperlimit & ~(row | ld | rd) which limit the 1 will only at chessboard’s length position(i.e, the result of ~(row | ld | rd) may be 101111…..0101, if the length of the chessboard is 4, only the last four bits is useful. Thus, we need to do this operation)。
while (pos!=0) if the value of pos is 0, it means no position on that row can the queen be put on.
pos & -pos means get the rightest 1.(-pos equals ~pos+1,you can read the related material about the bit operation)
pos=pos-p means that we put the rightest 1 to 0.(Thus, when in the next loop, the code will find the next rightest 1)
row+p means put the related bit from 0 to 1.
(ld + p)<< 1 left diagonal line must shift 1 for the next row.(Because it is diagonal line, the next one will shift 1,you can draw a matrix, it is easy to figure it out )
(rd + p)>> 1 right diagonal line must shift 1 for the next row(The same reason above.)
if (row!=upperlimit) means that every vertical line has a queen.(Because the variant only consider the vertical conflict(no diagonal),which means that every row has a queen. It means it has found a successful solution.)
The rest part is just backtracking which is the same as the solution to problem before.
Performance:
The running time is heavily reduced, which indicates high efficiency of the method.
Poly-Thinking 