其实这个问题老早之前我就做过了，但之前一直没发。

首先很容易想到使用枚举的方法

使用一个树结构来枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void f(int layer,int* prev_queen){//layer is 0-based,prev_queen数组代表之前的i行中queen所在的列
    int available[n];
    for(int i=0;i<n;i++){
        available[i]=1;
    }
    for(int i=0;i<layer;i++){
        int position=prev_queen[i];
        available[position]=0;//down
        int offset=layer-i;
        int left=position-offset;
        int right=position+offset;
        if(left>=0){
            available[left]=0;
        }
        if(right<n){
            available[right]=0;
        }
    }
    for(int i=0;i<n;i++){
        if(available[i]){
            if(layer==n-1){
                count++;
                return;
            }
            auto prev_queen_this=copy(prev_queen);//代表数组复制
            prev_queen_this[layer]=i;
            f(layer+1,prev_queen_this);
        }
    }
}

思考

不难发现，其实这个树的遍历用的是深度优先，我们根本没有必要复制一次这个prev_queen。
因为每次到达叶子节点的时候都能保证prev_queen中的值是正确的。

优化后完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include "iostream"
using namespace std;

int count=0;
const int n=8;
int prev_queen[n];
void f(int layer){//layer is 0-based
    int available[n];
    for(int i=0;i<n;i++){
        available[i]=1;
    }
    for(int i=0;i<layer;i++){
        int position=prev_queen[i];
        available[position]=0;//down
        int offset=layer-i;
        int left=position-offset;
        int right=position+offset;
        if(left>=0){
            available[left]=0;
        }
        if(right<n){
            available[right]=0;
        }
    }
    for(int i=0;i<n;i++){
        if(available[i]){
            if(layer==n-1){
                count++;
                return;
            }
            prev_queen[layer]=i;
            f(layer+1);
        }
    }
}

int main(){
    f(0);
    cout<<count<<endl;
    return 114514;
}