NQuenes
这道题目剪枝和不剪枝，性能天壤之别，如果每次都是到头了再判断是否解合法，N=8都要十几分钟，而如果在每一次想下层递归，都判断当前
摆放的皇后是否合法，N=10都只需要5s，因为这个是指数爆炸的搜索空间O(N^N)，空间，如果到最后解的话非常慢，而每次都会提前删减掉
很多无用解，减少很多次递归。
vector<string> board;
vector<pair<int,int>> qpos;
vector<vector<string> >solution;
void dfs(int level, int n);
vector<vector<string> > solveNQueens(int n) {
qpos.clear();
board.clear();
solution.clear();
string eachrow="";
for(int i=0;i<n;i++)
eachrow+='.';
for(int i=0;i<n;i++)
board.push_back(eachrow);
dfs(0,n);
return solution;
}
void dfs(int level, int n)
{
if(level>=n)
{
/*
for(int i=0;i<qpos.size();i++)
{
for(int j=0;j<i;j++)
{
if(qpos[j].second==qpos[i].second)
return ;
if((qpos[i].second-qpos[j].second)==(qpos[i].first-qpos[j].first))
return ;
if((qpos[i].first+qpos[i].second)==(qpos[j].first+qpos[j].second))
return ;
}
}*/
solution.push_back(board);
/*
int count=0;
for(int coli=0;coli<n;coli++)// each column has one q
{
int count=0;
for(int rowi=0;rowi<n;rowi++)
{
if(board[rowi][coli]=='Q')
count++;
if(count>=2)
return ;
}
}
for(int sum=0;sum<=2*(n-1);sum++)//second diagonal
{
int count=0;
for(int rowi=0;rowi<=n-1;rowi++)
{
int coli=sum-rowi;
if(coli<0 || coli >=n) continue;
if(board[rowi][coli]=='Q')
count++;
if(count>=2) return;
}
}
/*
for(int sum=n-2;sum>=0;sum--)
{
int count=0;
for(int rowi=0;rowi<=n-1;rowi++)
{
int coli=sum-rowi;
if(coli<0)break;
if(board[rowi][coli]=='Q')
count++;
if(count>=2) return ;
}
}*/
/*
for(int rowi=0;rowi<=n-1;rowi++)//main diagonal
{
int coli=0,count=0;
for(int i=0;i<=n-1;i++)
{
if(rowi+i>=n || coli+i >=n) break;
if(board[rowi+i][coli+i]=='Q')
count++;
if(count>=2) return ;
}
}
for(int coli=1;coli<=n-1;coli++)
{
int rowi=0,count=0;
for(int i=0;i<=n-2;i++)
{
if(rowi+i>=n || coli+i >=n) break;
if(board[rowi+i][coli+i]=='Q')
count++;
if(count>=2) return ;
}
}*/
}
else
{
for(int i=0;i<n;i++)
{
bool continueflag=false;
for(int j=0;j<qpos.size();j++)
{
if((qpos[j].second==i) || ((i-qpos[j].second)==(level-qpos[j].first)) || ((level+i)==(qpos[j].first+qpos[j].second)))
{
continueflag=true;
break ;
}
/*if((i-qpos[j].second)==(level-qpos[j].first))
continue ;
if((level+i)==(qpos[j].first+qpos[j].second))
continue ;*/
}
if(continueflag==true)
continue;
board[level][i]='Q';
qpos.push_back(make_pair(level,i));
dfs(level+1,n);
qpos.pop_back();
board[level][i]='.';
}
}
}
最后发现有个位运算的版本，看起来逼格很高的样子，虽然是递归但是很快，每次设置3个bitset分别表示列和两个对角线的被之前皇后禁止的位置，如果没到底，并且全部被禁止了，那么返回，无解，否则摆棋，同时添加新的皇后带来的三个方向上的禁止位置，如果到底了就返回结果，优势应该是体现在数据结构使用的优势上吧，因为之前是用matrix，然后每次判断的时候由于递归的参数不够，导致判断解是否合法是使用了大量的循环导致效率的降低。