面试题：C++递归函数优化八皇后问题

Question

八皇后问题是在8×8的棋盘上放置8个皇后，使得它们互不攻击（即任意两个皇后不能处于同一行、同一列或同一斜线上）。请用C++递归函数实现八皇后问题的求解，要求优化算法以减少不必要的计算，例如利用位运算等技巧，并说明优化思路和改进后的时间复杂度与空间复杂度。

Answer 1

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

class Solution {
private:
    int count = 0;
    vector<int> queens;
    vector<bool> columns;
    vector<bool> diagonals1;
    vector<bool> diagonals2;

    void backtrack(int row) {
        if (row == 8) {
            count++;
            return;
        }
        for (int col = 0; col < 8; col++) {
            int diagonal1 = row - col + 7;
            int diagonal2 = row + col;
            if (columns[col] || diagonals1[diagonal1] || diagonals2[diagonal2]) {
                continue;
            }
            queens[row] = col;
            columns[col] = true;
            diagonals1[diagonal1] = true;
            diagonals2[diagonal2] = true;
            backtrack(row + 1);
            columns[col] = false;
            diagonals1[diagonal1] = false;
            diagonals2[diagonal2] = false;
        }
    }

public:
    int totalNQueens(int n) {
        queens.resize(n);
        columns.resize(n, false);
        diagonals1.resize(2 * n - 1, false);
        diagonals2.resize(2 * n - 1, false);
        backtrack(0);
        return count;
    }
};

优化思路：

1. 利用位运算：通过位运算来表示列、主对角线和副对角线是否被占用，这样可以更高效地判断是否可以放置皇后。例如，使用一个整数的二进制位来表示列的占用情况，每一位对应棋盘的一列。对于对角线，同样可以通过一些计算得到对应的位表示。
2. 剪枝优化：在递归过程中，当发现某一行某一列或某条对角线已经被占用时，直接跳过该位置，不再继续向下递归，减少不必要的计算。

时间复杂度：理论上八皇后问题的时间复杂度为 (O(n!))，优化后通过剪枝减少了搜索空间，实际运行时间会远小于 (O(n!))，但严格来说仍然是指数级时间复杂度。 空间复杂度：使用了几个数组来记录列和对角线的占用情况，空间复杂度为 (O(n))。如果考虑递归调用栈的空间，在最坏情况下空间复杂度为 (O(n))，因为递归深度最大为 (n)。所以总的空间复杂度为 (O(n))。