信息奥赛一本通：1213八皇后问题

【题目描述】
在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。

【输入】
(无)

【输出】
按给定顺序和格式输出所有八皇后问题的解（见样例）。

【输入样例】
（无）
【输出样例】
No. 1
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
No. 2
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0
…以下省略

题解：

代码：

//1213：八皇后问题
#include<iostream>
using namespace std;
int a[9];//a[i]=j 记录第i行的皇后在j列 
int b[9];//b[j]=1 表示第j列有皇后了，=0表示第j列没有皇后
int qipan[9][9];//记录棋盘中的数字，有皇后的格子数字为1，没有皇后的格子为0 
int ysx[16];//表示从左下到右上的斜线,y=右，s=上，x=斜,总共15条斜线，每条斜线上所有格子 行号+列号=固定值，值范围2至16， 
int yxx[16];//表示从左上到右下的斜线,y=右，x=下，x=斜,总共15条斜线，每条斜线上所有格子 行号-列号=固定值 ，值范围7至-7 
int i,j,sum;//sum记录多少种可能 
void print();
void dfs(int i) //确定第i行皇后位置
{
	int j;
	for(j=1;j<=8;j++)
	{
		if(b[j]==0&&ysx[i+j]==0&&yxx[i-j+7]==0)//1.这一列没有皇后，2.这个点并不在某个皇后覆盖的从左下到右上的斜线上，3. 这个点并不在某个皇后覆盖的从左上到右下的斜线上
		{
			a[i]=j;
			b[j]=1;
			qipan[i][j]=1;
			ysx[i+j]=1;
			yxx[i-j+7]=1;
			if(i==8) 
			{
			//if(sum<3)
				print();
			}	
			else
				dfs(i+1);
			//以下为回溯 
			a[i]=0;
			b[j]=0;
			qipan[i][j]=0;
			ysx[i+j]=0;
			yxx[i-j+7]=0;
		}
	}
	return;
 }
void print()
{
	sum++;
	int m,n;
	cout<<"No. "<<sum<<endl;
	for(m=1;m<=8;m++)
	{
		for(n=1;n<=8;n++)
			{
				if(qipan[n][m]==1)
				cout<<"1"<<" ";
				else
				cout<<"0"<<" ";
			}
		cout<<endl;
	}
	return;
}
int main()
{
	dfs(1);
    return 0;
}