八皇后问题（洛谷p1219题解）

2020-07-24

八皇后问题是搜索中的经典问题，自己搞懂了然后偷偷发一篇题解
（反正也没人看我blog_(:з」∠)_）

直接进入正题：
首先是最重点的回溯和搜索部分

 void queen(int k) {
//    大于棋盘的大小即全部排完，所以就可以输出了 
    if( k > n ) {
        show();
        return; 
    }
    else {
        for(int i = 1 ; i <= n ; i++) {
//           每个点都进行尝试
            if( !b[i] && !c[i + k] && !d[n + k - i ]) {
//                     由于数组里的位置不能是负数，所以加个n
//                     借此保证每个都是正数
                a[i] = k;
                b[i] = 1;
                c[k + i] = 1;
                d[n + k - i] = 1;
//                    在每个点做上了标记，并准备进入下一轮循环 
                queen(k + 1);
                b[i] = 0;
                c[k + i] = 0;
                d[n - i + k] = 0; 
//                    这里清除掉标记
            }
        } 
    }
}

其次是输出问题 :
由于只要输出前三个，所以sum到3就不进行方法的输出了

   void show() {
    if( sum < 3 ) { 
        for(int i = 1 ; i <= n ; i++) {
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
    sum++;
}

最后再贴上完整的代码：

 #include<bits/stdc++.h>
using namespace std;

int a[10000], b[10000], c[10000], d[10000];
// a是行数，b为列数 ，c为左上到右下的对角线，d为左下到右上的对角线

int n , sum;
// n为棋盘的大小，sum为方法的个数 

void show() {
    if( sum < 3 ) { 
        for(int i = 1 ; i <= n ; i++) {
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
    sum++;
}

void queen(int k) {
//    大于棋盘的大小即全部排完，所以就可以输出了 
    if( k > n ) {
        show();
        return; 
    }
    else {
        for(int i = 1 ; i <= n ; i++) {
            if( !b[i] && !c[i + k] && !d[n + k - i ]) {
                a[i] = k;
                b[i] = 1;
                c[k + i] = 1;
                d[n + k - i] = 1;
//                在每个点做上了标记，并准备进入下一轮循环 
                queen(k + 1);
                b[i] = 0;
                c[k + i] = 0;
                d[n - i + k] = 0; 
            }
        } 
    }
} 


int main() {
    cin>>n;
//    读取棋盘的大小，但是棋盘的大小为全局变量 
    queen(1);
    cout<<sum<<endl;
//    输出拜访方法的数量 
    return 0; 
}

希望大家能够喜欢