n皇后
理清楚搜索顺序后就会比较清楚
从棋盘左上角的点开始 一列一列搜索 而每列又是自上而下进行搜索
C++ 代码
#include<iostream>
using namespace std;
const int N=20; //这里N定义最大数据的两倍主要与对角线的定义有关 在下面会提到
int n;
char g[N][N]; //定义了棋盘
bool row[N],col[N]; //row为行 col为列
bool dg[N],udg[N]; //dg为主对角线 udg为副对角线
void dfs(int x,int y,int s) //x为横坐标 y为纵坐标 s为皇后个数
{
if(y==n) //一列搜索完成 进入下一列搜索
{
y=0;
x++;
}
if(x==n) //所有列均搜索完毕
{
if(s==n) //由已知得皇后个数必然会与列数或者行数相等,从而才会输出结果
{
for(int i=0;i<n;i++)
puts(g[i]);
puts("");
}
return;
}
dfs(x,y+1,s); //上均不满足则进入下一行继续搜索
/*在正方形棋盘中主对角线x+y的值唯一 所以可以用x+y来表达主对角线
副对角线在x-y值唯一的情况 +n是为了保证值非负 即防止数组越界情况的发生 */
if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[x-y+n])
{
g[x][y]='Q'; //放置皇后
row[x]=col[y]=dg[x+y]=udg[x-y+n]=true; //标记足迹
dfs(x,y+1,s+1); //进入下一行继续搜索
//还原现场
g[x][y]='.';
row[x]=col[y]=dg[x+y]=udg[x-y+n]=false;
}
}
int main()
{
cin>>n;
//读入棋盘
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
g[i][j]='.';
dfs(0,0,0); //从左上角第一个点开始搜索 刚开始时皇后数为0
return 0;
}