八皇后问题解答

之前的解法是几年前的，勉勉强强能做出来，绝对算不上优雅，如今重做了，这是第二版

#include <iostream>
#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> getResult() {
        std::vector<std::vector<int>> result;

        std::vector<int> cur;
        dfs(result, 8, cur);
        return result;
    }

private:
    bool can_place(int target, const std::vector<int>& cur, int col) {
        std::vector<std::vector<bool>> matrix;
        for (int i = 0; i < target; i++) {
            matrix.push_back(std::vector<bool>(target, false));
        }

        for (int row = 0; row < cur.size(); row++) {
            int col = cur[row];
            for (int i = 0; i < target; i++) {
                matrix[row][i] = true;
                matrix[i][col] = true;
                int new_val = row + col - i;
                if (new_val >= 0 && new_val < target)
                    matrix[i][new_val] = true;
                new_val = i - row + col;
                if (new_val >= 0 && new_val < target)
                    matrix[i][new_val] = true;
            }
        }

        return !matrix[cur.size()][col];
    }

    void dfs(std::vector<std::vector<int>>& result, int target, const std::vector<int>& cur) {
        if (cur.size() == target) {
            result.push_back(cur);
            return;
        }

        for (int col = 0; col < target; col++) {
            auto new_cur = cur;
            if (!can_place(target, cur, col))
                continue;

            new_cur.push_back(col);
            dfs(result, target, new_cur);
        }
    }
};

int main() {
    auto result = Solution().getResult();
    for (int i = 0; i < result.size(); i++) {
        std::cout << std::endl;
        for (int j = 0; j < result[i].size(); j++) {
            std::cout << result[i][j] << " ";
        }
    }
    return 0;
}

第三版出来了

第三版用了个缓存matrix，速度会比第二种快

#include <iostream>
#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> get_result() {
        std::vector<std::vector<int>> result;

        std::vector<int> cur;
        dfs(result, 8, cur);
        return result;
    }

private:
    std::vector<std::vector<bool>> create_matrix(int target, const std::vector<int>& cur) {
        auto tmp_row = std::vector<bool>(target, false);
        std::vector<std::vector<bool>> matrix(target, tmp_row);
        for (int row = 0; row < cur.size(); row++) {
            const int col = cur[row];
            for (int i = 0; i < target; i++) {
                matrix[i][col] = true;
                matrix[row][i] = true;

                if (col + row - i >= 0 && col + row - i < target)
                    matrix[i][col + row - i] = true;
                if (col - row + i >= 0 && col - row + i < target)
                    matrix[i][col - row + i] = true;
            }
        }
        return matrix;
    }

    void dfs(std::vector<std::vector<int>>& result, int target, const std::vector<int>& cur) {
        if (cur.size() == target) {
            result.push_back(cur);
            return;
        }

        auto matrix = create_matrix(target, cur);
        for (int col = 0; col < target; col++) {
            if (matrix[cur.size()][col])
                continue;
            auto new_cur = cur;
            new_cur.push_back(col);
            dfs(result, target, new_cur);
        }
    }
};

int main() {
    auto result = Solution().get_result();
    std::cout << "result count: " << result.size() << std::endl;
    for (int i = 0; i < result.size(); i++) {
        std::cout << std::endl;
        for (int j = 0; j < result[i].size(); j++) {
            std::cout << result[i][j] << " ";
        }
    }
    return 0;
}