八皇后问题

题目描述:

要在国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃，皇后能吃同一行、同一列，同一对角线上（两个方向的对角线）的任意棋子。现在给一个整数n(n<=92)，输出前n种的摆法。

输入格式:

输入一个整数n。

输出格式:

输出共n行。

每行8个数，表示每行所放的列号，每个数输出占4列。

样例输入:

3

样例输出:

   1   5   8   6   3   7   2   4
   1   6   8   3   7   4   2   5
   1   7   4   6   8   2   5   3

提示:

八皇后总共的摆放方案有92种。

 

请仔细阅读下面程序：

#include <bits/stdc++.h>
using namespace std;
int a[20], b[20], c[20], d[9],n,num;

void print( ) {
	for (int i=1; i<=8; i++) printf( "%4d", d[i] );
	cout << '\n';
}

void dfs( int i ){  //搜索第i行，准备在第i行摆放皇后 
	if (i>8) {		//递归边界，8行都放满了，打印棋盘 
		num++;
		if ( num <= n ) print();
		return;
	}
	//在当前行，从第1列到第8列，一列列去试放皇后
	for (int j=1; j<=8; j++){	//搜索第i行的8列
		//如果当前行，当前列可以放皇后，那么就在该位置放皇后
		if (a[ i+j ]==0 && b[ i-j+7 ]==0 && c[ j ]==0){//如何判断第i行第j列，能不能放皇后 
			a[ i+j ] = 1; //把该位置的和值差值及列（即两条对角线和列），做上不能再放的标志
			b[ i-j+7 ]= 1;	//思考为什么要加上7
			c[ j ] = 1;
			d[ i ] = j;		//第i行放在第j列
			dfs( i+1 );		//进入下一行
			a[ i+j ] = 0;	//回到该行后，我们先解除不能放的标志，然后接着去试下一列
			b[ i-j+7 ] = 0;
			c[ j ] = 0;
		}
	}
}

int main(){
	cin >> n;
	dfs( 1 );
	return 0;
}

时间限制: 1000ms
空间限制: 128MB

---

来源: 原创