[Leetcode]51. N-Queens(C++)

题目描述

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

例子

见官网例子。

Constraints

1 <= n <= 9

解题思路

求所有可能解的问题通常都是用回溯法进行暴力遍历加剪枝。这道题也是一样，通过遍历每一行，在遍历某行时，遍历每一列位置，检查该位置对应的列以及对角线是否有棋子，如果没有则添加该棋子，递归地求解下一行。代码如下：

#include <string>
#include <unordered_set>
#include <vector>

class Solution {
public:
    std::vector<std::vector<std::string>> solveNQueens(int n) {
        std::vector<std::vector<std::string>> result;
        std::unordered_set<int> col_used;
        std::unordered_set<int> diag1;
        std::unordered_set<int> diag2;
        std::vector<std::string> curr;
        dfs(0, n, col_used, diag1, diag2, curr, result);
        return result;
    }

private:
    void dfs(int row, int n, std::unordered_set<int>& col_used,
             std::unordered_set<int>& diag1, std::unordered_set<int>& diag2,
             std::vector<std::string>& curr,
             std::vector<std::vector<std::string>>& result) {
        if (row == n) {
            result.push_back(curr);
            return;
        }

        std::string curr_row(n, '.');
        for (int col = 0; col < n; ++col) {
            if (col_used.count(col) || diag1.count(col - row) ||
                diag2.count(col + row))
                continue;
            curr_row[col] = 'Q';
            col_used.insert(col);
            diag1.insert(col - row);
            diag2.insert(col + row);
            curr.push_back(curr_row);
            dfs(row + 1, n, col_used, diag1, diag2, curr, result);
            curr.pop_back();
            curr_row[col] = '.';
            col_used.erase(col);
            diag1.erase(col - row);
            diag2.erase(col + row);
        }
    }
};

时间复杂度: O(n!)
空间复杂度: O(n)

GitHub 代码同步地址： 51.NQueens.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions