[Leetcode] N-Queens 系列

N-Queens 系列题解

题目来源：

N-Queens

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

board

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.

For example,

There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Solution

class Solution {
private:
    int dimension;

    inline bool onDiagonal(int r1, int r2, int c1, int c2) {
        int rowDis = r1 - r2;
        int colDis = c1 - c2;
        return rowDis == colDis || -rowDis == colDis;
    }

    bool isValid(const vector<string>& board, int row, int col) {
        if(row == 0)
            return true;
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < dimension; c++) {
                if (board[r][c] == 'Q' &&
                        (c == col || onDiagonal(r, row, c, col)))
                    return false;
            }
        }
        return true;
    }

    void backTrack(vector<vector<string>>& res,
                   vector<string>& board, int row) {
        if (row == dimension) {
            res.push_back(board);
        } else {
            for (int col = 0; col < dimension; col++) {
                if (isValid(board, row, col)) {
                    board[row][col] = 'Q';
                    backTrack(res, board, row + 1);
                    board[row][col] = '.';
                }
            }
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        if (n == 0)
            return res;
        dimension = n;
        vector<string> board(dimension, string(dimension, '.'));
        backTrack(res, board, 0);
        return res;
    }
};

解题描述

这道题就是经典的N皇后问题，要求在给出的n×n的棋盘上放置n个皇后，皇后之前不会互相击杀（不在同一行、同一列、同一对角线上）。上面用到的是递归回溯的办法，每次确定新一行上的皇后，添加新一行的时候要检验与之前行上的皇后是否会相互击杀。

更优解法

2018.2.27更新

评估上面的解法，其实还是存在可以优化的空间。对整个递归回溯解法来说，对特定的维度n来说，递归的层数是固定的，所以时间复杂度主要取决于位置合法性检查，而细想可知，其实上面的解法中合法性检查部分做了很多不必要的操作：遍历棋盘来找到存在皇后的位置。而对整个棋盘而言，我们需要检查的位置其实对每个维度来说是固定的：

n个列
2n - 1条左对角线
2n - 1条右对角线

权衡利弊，我们可以采用以空间换时间的办法，记录上述5n -2个位置上的皇后占据情况来降低检查的时间复杂度。下面给出具体实现：

class Solution {
private:
    int dimension;
    vector<bool> colFlags, leftDiaFlags, rightDiaFlags;

    void backTrack(vector<vector<string>>& res,
                   vector<string>& board, int row) {
        if (row == dimension) {
            res.push_back(board);
            return;
        }
        for (int col = 0; col < dimension; col++) {
            if (!colFlags[col] &&
                    !leftDiaFlags[dimension - 1 + row - col] &&
                    !rightDiaFlags[row + col]) {
                colFlags[col]
                        = leftDiaFlags[dimension - 1 + row - col]
                        = rightDiaFlags[row + col]
                        = true;
                board[row][col] = 'Q';
                backTrack(res, board, row + 1);
                board[row][col] = '.';
                colFlags[col]
                        = leftDiaFlags[dimension - 1 + row - col]
                        = rightDiaFlags[row + col]
                        = false;
            }
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        if (n == 0)
            return res;
        dimension = n;
        vector<string> board(dimension, string(dimension, '.'));
        // 三种位置上的皇后是否存在的标记：
        colFlags.resize(dimension, false); // 1. 列
        leftDiaFlags.resize(2 * dimension - 1, false); // 2. 左对角线
        rightDiaFlags.resize(2 * dimension - 1, false); // 3. 右对角线
        backTrack(res, board, 0);
        return res;
    }
};

N-Queens II

这道题题意只要求求出N皇后解法数目，不要求给出具体解法，则与第一版差别不大，只需略作修改。

Solution

class Solution {
private:
    int dimension;
    vector<bool> colFlags, leftDiaFlags, rightDiaFlags;

    void backTrack(int& res, int row) {
        if (row == dimension) {
            ++res;
            return;
        }
        for (int col = 0; col < dimension; col++) {
            if (!colFlags[col] &&
                !leftDiaFlags[dimension - 1 + row - col] &&
                !rightDiaFlags[row + col]) {
                colFlags[col]
                        = leftDiaFlags[dimension - 1 + row - col]
                        = rightDiaFlags[row + col]
                        = true;
                backTrack(res, row + 1);
                colFlags[col]
                        = leftDiaFlags[dimension - 1 + row - col]
                        = rightDiaFlags[row + col]
                        = false;
            }
        }
    }
public:
    int totalNQueens(int n) {
        int res = 0;
        if (n == 0)
            return res;
        dimension = n;
        // 三种位置上的皇后是否存在的标记：
        colFlags.resize(dimension, false); // 1. 列
        leftDiaFlags.resize(2 * dimension - 1, false); // 2. 左对角线
        rightDiaFlags.resize(2 * dimension - 1, false); // 3. 右对角线
        backTrack(res, 0);
        return res;
    }
};