八皇后(dfs的充分运用)

解题思路:

由于问题对行列对角线都有限制，可以设置几个布尔类型的数组来保存状态，从行开始增加对安全对位的寻找。

注意事项:

参考代码:

#include<iostream>

#include<vector>

using namespace std;

int N;

vector<int>solution;

vector<int>col_used;

vector<int>diag1;

vector<int>diag2;

vector<vector<int>>all_solutions;

int total_counts = 0;

void dfs(int row)

{

    if(row == N)

    {

        if(all_solutions.size() < 3)

        {

            all_solutions.push_back(solution);

        }

        total_counts++;

        return;

    }

    for(int col = 0; col < N; col++)

    {

        //如果列有元素则结束这一列的判断

        if(col_used[col]) continue;

        //如果主副对角线有元素则也结束

        int d1 = row - col + N - 1;//主对角线需要加偏移量保证数组起点为0

        int d2 = row + col;

        if(diag2[d2] || diag1[d1]) continue;

        //这个点位安全，放置元素

        col_used[col] = true;

        diag1[d1] = true;

        diag2[d2] = true;

        solution[row] = col;

        //判断下一行

        dfs(row + 1);

        //回溯

        col_used[col] = false;

        diag1[d1] = false;

        diag2[d2] = false;

    }

}

int main()

{

    cin >> N;

    col_used.assign(N, false);

    solution.assign(N, 0);

    diag1.assign(2 * N - 1, false);

    diag2.assign(2 * N - 1, false);

    dfs(0);

    for(int i = 0; i < 3; i++)

    {

        for(int j = 0; j < solution.size(); j++)

        {

            cout << all_solutions[i][j] + 1 << " ";//调整列号从1开始

        }

        cout << endl;

    }

    cout << total_counts << endl;

    return 0;

}