八皇后

题目描述

一个如下的6×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。
上面的布局可以用序列2 4 6 1 3 5 来描述，第 i 个数字表示在第i 行的相应位置有一个棋子，如下：

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

输入格式

一行一个正整数，表示棋盘是n×n 大小的。

输出格式

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

代码部分

方法一：（全排列的优化）

#include <bits/stdc++.h>
using namespace std;
const int N=200;//数组要开的够大
int n,way[N],y[N],zd[N],fd[N],cnt;
void dfs(int u)
{
	if(u==n+1)
	{
		if(cnt<3)
		{
			for(int i=1;i<=n;i++) printf("%d ",way[i]);
			puts("");
		}
		cnt++;
		return ; 
	}
	for(int i=1;i<=n;i++)
	{
		if(!y[i]&&!zd[u+i]&&!fd[i-u+n])
		{
			y[i]=1;
			zd[u+i]=1;
			fd[i-u+n]=1;
			way[u]=i;
			dfs(u+1);
			way[u]=0;
			y[i]=0;
			zd[u+i]=0;
			fd[i-u+n]=0;
		}
	} 
}
int main ()
{
	cin>>n;
	dfs(1);
	cout<<cnt<<endl;
	return 0;	
}

方法二：（纯爆搜）

#include <bits/stdc++.h>
using namespace std;
const int N=20;
int n,way[N],x[N],y[N],zd[N],fd[N],cnt;
void dfs(int u,int i,int s)
{
	if(s>n) return;
	if(i==n+1) i=1,u++;
	if(u==n+1)
	{
		if(s==n)
		{
			if(cnt<3)
			{
				for(int i=1;i<=n;i++) printf("%d ",way[i]);
				puts("");
			}
			cnt++;
		}
		return;
	}
	if(!x[u]&&!y[i]&&!zd[u+i]&&!fd[i-u+n])
	{
		x[u]=y[i]=zd[u+i]=fd[i-u+n]=1;
		way[u]=i;
		dfs(u,i+1,s+1);
		way[u]=0;
		x[u]=y[i]=zd[u+i]=fd[i-u+n]=0;
	}
	
	dfs(u,i+1,s);
}
int main ()
{
	cin>>n;
	dfs(1,1,0);
	cout<<cnt<<endl;
	return 0;	
}

• 可惜只能过60%的样例，我真的太菜了，那位大佬有其他想法，希望可以给我指点一二！ 跪谢！