八皇后问题

提交数: 1334, 通过率: 53%, 平均分: 54.09

题目描述:

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

1497315157753049269.jpeg

输入格式:

输入一个整数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

提示:

1497344390503583632.png

八皇后总共的摆放方案有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

来源: 原创