目录

• 1. 分析（朴素思路）
• 2. 代码（朴素代码）
• 3. 上述代码的问题
• 4. 改进的代码

1. 分析（朴素思路）

枚举每个位置，枚举完一次，下一次（dfs）从下一行开始重新枚举。

注意三点：

• 如何判断在同一斜线（y = x + b & y = -x + b）
• 每次排除一行或一列，否则会有重复输出。每次最多排除一行或一列，否则如果同时排除一行和一列则无法输出正确答案。
• 利用标记 continue。

2. 代码（朴素代码）

#include<iostream>

#define _rep_le(i, a, b) for(int i = (a); i <= (b); ++ i)
#define _rep_lt(i, a, b) for(int i = (a); i < (b); ++ i)
#define _rrep_ge(i, a, b) for(int i = (b); i >= (a); -- i)
#define _rrep_gt(i, a, b) for(int i = (b); i > (a); -- i)

using namespace std;

const int N = 10;

int n;
bool visitedCol[N], visitedRow[N], visitedSlide[2*N], visitedSlideR[2*N];
bool board[N][N];

void dfs(int row, int level) {
    if(level >= n) {
        _rep_lt(i, 0, n) {
            if(board[i][0] == false) cout << ".";
            else cout << "Q";
            _rep_lt(j, 1, n) {
                if(board[i][j] == false) cout << ".";
                else cout << "Q";
            }
            cout << endl;
        }
        cout << endl;
        return;
    }

    _rep_lt(i, row, n) {
        // for row
        if(visitedRow[i] == true) continue;
        _rep_lt(j, 0, n) {
            // for col
            if(visitedCol[j] == true) continue;
            if(visitedSlide[i-j+n] == true) continue;
            if(visitedSlideR[i+j] == true) continue;

            // Set Env
            /**
             * From y = x + b & y = -x + b, the relationship between
             * horizontal and vertical coordinates on the same oblique
             * lines can be obtained.
             * i.e. b = y - x & b = y + x
             */ 
            visitedRow[i] = true;
            visitedCol[j] = true;
            visitedSlide[i-j+n] = true;
            visitedSlideR[i+j] = true;
            board[i][j] = true;

            /**
             * If donot start from next line, there will be duplicate content.
             * Each recursion will exclude at most one row or one column,
             * and cannot reduce one row & one column at the same time.
             */ 
            dfs(i + 1, level + 1);

            // Recover Env
            visitedRow[i] = false;
            visitedCol[j] = false;
            visitedSlide[i-j+n] = false;
            visitedSlideR[i+j] = false;
            board[i][j] = false;
        }
    }

}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    dfs(0, 0);

    return 0;
}

3. 上述代码的问题

“每次排除了一行下一次枚举下一行”这样的操作意味着同一行不可能重复选到。因此对于行的标记是没有意义的。

此外，在一次 dfs 中枚举完一行后，枚举下一行的时候，后面的行不可能枚举到前面的行，因此当前行不选一个位置，直接枚举下一行也是没有意义的。

因此我们的操作其实是：每次在对应的一行中枚举不同的位置，选择好后对下一行进行相同操作（dfs）直到每一行都选择完毕，然后输出一个答案。

4. 改进的代码

#include<iostream>

#define _rep_le(i, a, b) for(int i = (a); i <= (b); ++ i)
#define _rep_lt(i, a, b) for(int i = (a); i < (b); ++ i)
#define _rrep_ge(i, a, b) for(int i = (b); i >= (a); -- i)
#define _rrep_gt(i, a, b) for(int i = (b); i > (a); -- i)

using namespace std;

const int N = 10;

int n;
bool visitedCol[N], visitedSlide[2*N], visitedSlideR[2*N];
bool board[N][N];

void dfs(int row) {
    if(row >= n) {
        _rep_lt(i, 0, n) {
            if(board[i][0] == false) cout << ".";
            else cout << "Q";
            _rep_lt(j, 1, n) {
                if(board[i][j] == false) cout << ".";
                else cout << "Q";
            }
            cout << endl;
        }
        cout << endl;
        return;
    }

    _rep_lt(j, 0, n) {
        // for col
        if(visitedCol[j] == true) continue;
        if(visitedSlide[row-j+n] == true) continue;
        if(visitedSlideR[row+j] == true) continue;

        // Set Env
        /**
         * From y = x + b & y = -x + b, the relationship between
         * horizontal and vertical coordinates on the same oblique
         * lines can be obtained.
         * i.e. b = y - x & b = y + x
         */ 
        visitedCol[j] = true;
        visitedSlide[row-j+n] = true;
        visitedSlideR[row+j] = true;
        board[row][j] = true;

        /**
         * If donot start from next line, there will be duplicate content.
         * Each recursion will exclude at most one row or one column,
         * and cannot reduce one row & one column at the same time.
         */ 
        dfs(row + 1);

        // Recover Env
        visitedCol[j] = false;
        visitedSlide[row-j+n] = false;
        visitedSlideR[row+j] = false;
        board[row][j] = false;
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    dfs(0);

    return 0;
}