八皇后问题
提交数: 1334, 通过率: 53%, 平均分: 54.09
题目描述:
要在国际象棋棋盘中放八个皇后,使任意两个皇后都不能互相吃,皇后能吃同一行、同一列,同一对角线上(两个方向的对角线)的任意棋子。现在给一个整数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
来源: 原创