1213：八皇后问题(c++)

前言：这是一道众周所知的经典问题，十分的耐人寻味。以下是题目以及题解。

【题目描述】

【输入】

【输出】

【输入样例】

（无）

【输出样例】

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 
...以下省略

思路

首先千万不要忘了有两个及以上的其他函数时要在代码开头声明！！！

其次，No.后有个空格！N大写o小写！”No. "

说正经的首先，我们表示棋盘不能潦草的就用一个二维带过，如果用二维数组在回溯的时候会肥肠马饭。So用了一个一维数组a表示，下标当行数，值是列数。还得判断这歌皇后安全否，then建立b，c，d确保行列对角线上只有一个皇后.

题解

#include <bits/stdc++.h>
using namespace std;
int k,l=0;
int a[9],c[17],b[9],d[17];
void print();
void f(int k){
? ? for(int i=1;i<=8;i++){
? ? ? ? if(!b[i]&&(!c[i+k]&&(!d[k-i+7]))){
? ? ? ? ? ? a[k]=i;
? ? ? ? ? ? b[i]=1;
? ? ? ? ? ? c[k+i]=1;
? ? ? ? ? ? d[k-i+7]=1;
? ? ? ? ? ? if(k==8)print();
? ? ? ? ? ? else f(k+1);
? ? ? ? ? ? b[i]=0;
? ? ? ? ? ? c[i+k]=0;
? ? ? ? ? ? d[k-i+7]=0;
? ? ? ? }
? ? }
}
void print(){
? ? l++;
? ? cout<<"No. "<<l<<endl;
? ? for(int i=1;i<=8;i++){
? ? ? ? for(int j=1;j<=8;j++){
? ? ? ? ? ? if(a[j]==i){
? ? ? ? ? ? ? ? for(int m=1;m<j;m++)
? ? ? ? ? ? ? ? ? ? cout<<'0'<<' ';
? ? ? ? ? ? ? ? cout<<1<<' ';
? ? ? ? ? ? ? ? for(int m=1;m<=8-j;m++){
? ? ? ? ? ? ? ? ? ? cout<<'0'<<' ';
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? cout<<endl;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
int main(){
? ? f(1);
? ? return 0;
}