n皇后

这个整体的思路就是要回溯,如果当前的不能放,那么就回去,然后我们分析可以发现位于对角线上的皇后有规律

主对角线:y=x+b——>x-y=b

副对角线:y=-x+b——>x+y=b

所以我们可以开两个数组来进行存储当前位置的对角线是否有皇后占领

这是第一种方式,按照行数来直接判断

#include<iostream>
using namespace std;
const int N=15;
int a[N];
bool zd[2*N+1],fd[2*N+1],vis[N];
int n;
void dfs(int x)
{
	if(x>n)
    {
    	for(int i=1;i<=n;i++)
        {
        	for(int j=1;j<=n;j++)
            {
            	if(a[i]==j)cout<<'Q';
                else cout<<'.';
            }
            cout<<endl;
        }
        cout<<endl;
    	return ;
    }
    for(int i=1;i<=n;i++)
    {
    	if(!vis[i]&&!zd[x-i+n]&&!fd[x+i])
        {
        	vis[i]=zd[x-i+n]=fd[x+i]=true;
            a[x]=i;
            vis[i]=zd[x-i+n]=fd[x+i]=false;
        }
    }
}
int main()
{
	cin>>n;
    dfs(1);
    return 0;
}

第二种方式,按照点来进行

根据当前点是否放皇后来进行,如果当前要放的位置超出边界了,就可以让y=0,x++,这里一定要注意先放完再判断皇后是否已经到位

#include<iostream>
using namespace std;
const int N=15;
char path[N][N];
int n;
bool zd[2*N+1],fd[2*N+1],c[N],r[N];
void dfs(int x,int y,int s)
{
	if(s>n)return;
    if(y==n)y=0,x++;
    if(x==n)
    {
    	if(s==n)
    	{
    		for(int i=0;i<n;i++)
        		puts(path[i]);
            puts("");
    	}
        return ;
    }
    path[x][y]='.';
    dfs(x,y+1,s);//当前位置不放皇后
    if(!r[x]&&!c[y]&&!zd[x-y+n]&&!fd[x+y])
    {
    	r[x]=c[y]=zd[x-y+n]=fd[x+y]=true;
        path[x][y]='Q';
        dfs(x,y+1,s+1);//当前位置放皇后
        r[x]=c[y]=zd[x-y+n]=fd[x+y]=false;
        path[x][y]='.';
    }
}
int main()
{
	cin>>n;
    dfs(0,0,0);
    return 0;
}