问题描述

输入一个数N，要求输出满足N皇后规则的所有皇后位置的情况。

利用递归的思想，可以有效的解决这个问题。

我们可以假设前 k - 1行都没有发生冲突，现在需要决定 第 k 行的皇后位置。

我们只需要判断某位置是否与前 k -1行的皇后是否冲突即可，不冲突就可以放置，然后继续下一轮的放置（此处利用递归）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int queenPos[100]; // 假设最多不超过N个皇后，此处用于存放每一行的皇后的列数
int N = 66;
void NQueen(int k){ // 假设前 k - 1行已经完毕，需要放置第 k 行
    if(k == N){
        for(int i = 0; i < N; i++){
            cout << queenPos[i] << "->";
        }
        cout << endl;
        return;
    }
    // 确定一个与已经放置的皇后位置不冲突的位置
    for(int i = 0; i < N; i++){  // 尝试所有位置，判断是否冲突
        int j = 0;
        for(j = 0; j < k; j++){
            if(queenPos[j] == i || abs(k - j) != abs(i - queenPos[j]))
                break;
        }
        if(j == k){ // 无冲突
            queenPos[k] = i; // 放置在该位置
            NQueen(k+1);     // 确定下一行
        }
    }
}