DFS算法经典题目： Leetcode 51.N皇后

DFS算法经典题目： Leetcode 51.N皇后

题目详情如下

这道题如果使用暴力解法的话，需要对N个皇后放在每个地方都进行枚举并判断是否可行，时间复杂度非常之高，肯定是过不了的，所以需要使用其他解法。

根据题目可以知道每两个皇后之间的位置关系不能是在同一条直线或同一条斜线上。所以，每个皇后只能位于不同行不同列。每一行有且只有一个皇后，每一列有且只有一个皇后，且任何两个皇后不能位于一条斜线上，所以想到了DFS算法解决，主要思路即是回溯。

具体做法是：使用一个数组记录每行放置的皇后的下标，一次在每一行放置一个皇后，每次放置的新皇后不能与前N行放置的皇后在同一条直线或斜线上，并更新此次放置皇后的下标。当N个皇后都放置完毕，这个即是一个解，再将这数组转换为棋盘状态返回。

由于每个皇后必须位于不同行不同列，所以第一个皇后有N种选择可以放置，第二个皇后便是少一种选择，以此类推，最后的时间复杂度是O(N!)

代码思路

为了判断一个位置所在的直线或斜线上是否有其他皇后，使用三个hash set记录列以及两个方向的斜线是否有其他皇后。

列的话使用下标即可表示。

而斜线的话，从左上到右下的斜线，每个位置满足行下标与列下表之差相等，例如(0,0)与(1,1)在一条线上；

从右上到左下的斜线，每个位置满足行下标与列下表之和相等，例如(0,1)与(1,0)在一条线上。

所以在判断时，对于每个位置判断是否在三个集合中，如果都不在，则当前位置可放置。

上代码：

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        auto solutions = vector<vector<string>>();
        auto queens = vector<int>(n, -1);
        auto columns = unordered_set<int>();
        auto diagonals1 = unordered_set<int>();
        auto diagonals2 = unordered_set<int>();
        DFS(solutions, queens, n, 0, columns, diagonals1, diagonals2);
        return solutions;
    }

    void DFS(vector<vector<string>> &solutions, vector<int> &queens, int n, int row, unordered_set<int> &columns, unordered_set<int> &diagonals1, unordered_set<int> &diagonals2) {
        if (row == n) {
            vector<string> board = generateBoard(queens, n);
            solutions.push_back(board);
        } else {
            for (int i = 0; i < n; i++) {
                if (columns.find(i) != columns.end()) {
                    continue;
                }
                int diagonal1 = row - i;
                if (diagonals1.find(diagonal1) != diagonals1.end()) {
                    continue;
                }
                int diagonal2 = row + i;
                if (diagonals2.find(diagonal2) != diagonals2.end()) {
                    continue;
                }
                queens[row] = i;
                columns.insert(i);
                diagonals1.insert(diagonal1);
                diagonals2.insert(diagonal2);
                DFS(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
                queens[row] = -1;
                columns.erase(i);
                diagonals1.erase(diagonal1);
                diagonals2.erase(diagonal2);
            }
        }
    }

    vector<string> generateBoard(vector<int> &queens, int n) {
        auto board = vector<string>();
        for (int i = 0; i < n; i++) {
            string row = string(n, '.');
            row[queens[i]] = 'Q';
            board.push_back(row);
        }
        return board;
    }
};

复杂度分析

时间复杂度：O(N!)

空间复杂度：O(N)，其中 N 是皇后数量。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合，递归调用层数不会超过 N，数组的长度为 N，每个集合的元素个数都不会超过 N。