题目

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

简析

经典的八皇后问题，国际象棋里的皇后比较NB，即能直着走，也能斜着走。皇上只能走一步。可能东西文化差异吧，中国象棋就没皇后，可能后宫佳丽太多，不知道上哪个好。
这么厉害的皇后，一个八成八棋盘能不能容下八个共存呢？这就是八皇后问题。
解法有很多，用二维数组模拟一个期盼，我们采用一行一行放，即在第一行找个地方放一个，然后搜索第二行看能不能找到放的地方，直到在第八行找到地方为止。

1 for循环范围

对于第K层，就是第K行，我们从第一列一直尝试放到第八列，那范围就是1～8即可。

    for(int i=1;i<=8;i++){

2 判断可选

判断一个点能不能放，有四种情况

• A 左边
• B 上边
• C 左上
• D 右上
  这块是这种解法中的重难点部分，大家自己画一下就懂了。为什么下边、左下，右下都不用判断呢？

bool pd(int x,int y){
    for(int l=y-1;l>=1;l--){//这一行往前
        if(vis[x][l]==1) return false;
    }
    for(int h=x-1;h>=1;h--){//往上
        if(vis[h][y]==1) return false;
    }
    for(int h=x-1,l=y-1;h>=1&&l>=1;h--,l--){//左上
        if(vis[h][l]==1) return false;
    }
    for(int h=x-1,l=y+1;h>=1&&l<=8;h--,l++){//右上
        if(vis[h][l]==1) return false;
    }
    return true;
}

3 选中、结束条件、递归方法

• 选中后，这个点标为1即可
• 结束条件：如果选完了，k=8，说明第八行也找到了，打印就行了。
• 递归方法：没到第八行，搜索下一层
• 回溯：把这个点重新设为0

代码

#include <iostream>
using namespace std;
int vis[9][9]={0};
int total=0;
bool pd(int,int);
void print(){
    total++;
    for(int i=1;i<=8;i++){
        for(int j=1;j<=8;j++){
            if(vis[i][j]==0) cout<<"O ";
            else cout<<"X ";
        }
        cout<<endl;
    }
    cout<<endl;
}
void search(int k){
    for(int i=1;i<=8;i++){
        if(pd(k,i)){
            vis[k][i]=1;
            if(k==8) print();
            search(k+1);
            vis[k][i]=0;
        }
    }
}
bool pd(int x,int y){
    for(int l=y-1;l>=1;l--){//这一行往前
        if(vis[x][l]==1) return false;
    }
    for(int h=x-1;h>=1;h--){//往上
        if(vis[h][y]==1) return false;
    }
    for(int h=x-1,l=y-1;h>=1&&l>=1;h--,l--){//左上
        if(vis[h][l]==1) return false;
    }
    for(int h=x-1,l=y+1;h>=1&&l<=8;h--,l++){//右上
        if(vis[h][l]==1) return false;
    }
    return true;
}
int main(){
    search(1);
    cout<<total;
}