[LeetCode] 51. N-Queens

[grandyang]

请点击下方图片观看讲解视频
Click below image to watch YouTube Video

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. You may return the answer in any order.

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

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]] 

Constraints:

• 1 <= n <= 9

经典的N皇后问题，基本所有的算法书中都会包含的问题。可能有些人对国际象棋不太熟悉，大家都知道中国象棋中最叼的是车，横竖都能走，但是在国际象棋中还有更叼的，就是皇后，不但能横竖走，还能走两个斜线，有如 bug 一般的存在。所以经典的八皇后问题就应运而生了，在一个 8x8 大小的棋盘上如何才能放8个皇后，使得两两之间不能相遇，所谓一山不能容二虎，而这里有八个母老虎，互相都不能相遇。对于这类问题，没有太简便的方法，只能使用穷举法，就是尝试所有的组合，每放置一个新的皇后的时候，必须要保证跟之前的所有皇后不能冲突，若发生了冲突，说明当前位置不能放，要重新找地方，这个逻辑非常适合用递归来做。

我们先建立一个长度为 nxn 的全是点的数组 queens，然后从第0行开始调用递归。在递归函数中，首先判断当前行数是否已经为n，是的话，说明所有的皇后都已经成功放置好了，所以只要将 queens 数组加入结果 res 中即可。否则的话，遍历该行的所有列的位置，行跟列的位置都确定后，我们要验证当前位置是否会产生冲突，那么就需要使用一个子函数来判断了，首先验证该列是否有冲突，就遍历之前的所有行，若某一行相同列也有皇后，则冲突返回 false；再验证两个对角线是否冲突，就是一些坐标转换，注意不要写错了，若都没有冲突，则说明该位置可以放皇后，放了新皇后之后，再对下一行调用递归即可，注意递归结束之后要返回状态，参见代码如下：

解法一：

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> queens(n, string(n, '.'));
        dfs(0, queens, res);
        return res;
    }
    void dfs(int row, vector<string>& queens, vector<vector<string>>& res) {
        int n = queens.size();
        if (row == n) {
            res.push_back(queens);
            return;
        }
        for (int j = 0; j < n; ++j) {
            if (isValid(queens, row, j)) {
                queens[row][j] = 'Q';
                dfs(row + 1, queens, res);
                queens[row][j] = '.';
            }
        }
    }
    bool isValid(vector<string>& queens, int row, int col) {
        for (int i = 0; i < row; ++i) {
            if (queens[i][col] == 'Q') return false;
        }
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
            if (queens[i][j] == 'Q') return false;
        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < queens.size(); --i, ++j) {
            if (queens[i][j] == 'Q') return false;
        }
        return true;
    }
};

我们还可以只使用一个一维数组 queenCol 来保存所有皇后的列位置，初始化均为 -1， 那么 queenCol[i] 就是表示第i个皇后在 (i, queenCol[i]) 位置，递归函数还是跟上面的解法相同，就是在当前行数 row 等于n的时候，要新建一个 n by n 的矩阵 cur，把 queenCol 中保存的皇后的位置赋值到 cur 中，并将 cur 存入结果 res 中。这种记录每个皇后的坐标的方法在验证冲突的时候比较简单，只要从第0行遍历到当前行，若跟之前的皇后的列数相同，直接返回 false，叼就叼在判断对角线冲突非常简便，因为当两个点在同一条对角线上，那么二者的横坐标差的绝对值等于纵坐标差的绝对值，利用这条性质，可以快速的判断冲突，代码如下：

解法二：

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<int> queenCol(n, -1);
        dfs(0, queenCol, res);
        return res;
    }
    void dfs(int row, vector<int>& queenCol, vector<vector<string>>& res) {
        int n = queenCol.size();
        if (row == n) {
            vector<string> cur(n, string(n, '.'));
            for (int i = 0; i < n; ++i) {
                cur[i][queenCol[i]] = 'Q';
            }
            res.push_back(cur);
            return;
        }
        for (int j = 0; j < n; ++j) {
            if (isValid(queenCol, row, j)) {
                queenCol[row] = j;
                dfs(row + 1, queenCol, res);
                queenCol[row] = -1;
            }
        }
    }
    bool isValid(vector<int>& queenCol, int row, int col) {
        for (int i = 0; i < row; ++i) {
            if (col == queenCol[i] || abs(row - i) == abs(col - queenCol[i])) return false;
        }
        return true;
    }
};

Github 同步地址：

#51

类似题目：

N-Queens II

Grid Illumination

参考资料：

https://leetcode.com/problems/n-queens/

http://www.cnblogs.com/TenosDoIt/p/3801621.html

https://leetcode.com/problems/n-queens/discuss/19805/My-easy-understanding-Java-Solution

https://leetcode.com/problems/n-queens/discuss/19808/Accepted-4ms-c%2B%2B-solution-use-backtracking-and-bitmask-easy-understand.

LeetCode All in One 题目讲解汇总(持续更新中...)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

喜欢请点赞，疼爱请打赏❤️~.~

微信打赏

|

Venmo 打赏

---|---

[lld2006]

可以做些优化。
1， 逐行检查， 各用一个n bit的flag来检查diagonal, offdiag以及column被占用的情况。如果某列满足均未占用， 在flag上该列做标记。 下一行做检查前， 将主对角线flag右移一位， 付对角线flag左移一位即可

2，逐行检查时， 第一行的col只用检查一半， 另外一半可以通过对称性得到（没有写在code中）
3, github 对贴code不友好啊， 括号什么的我就不改了。 看source可以看到正确的。

class Solution {
public:
    vector> solveNQueens(int n) {
      vector columns(n, -1);//which column is used for each row
      trace(0, columns, 0, 0, 0, n);
      return results_;
    }
    void trace(int row, vector& columns, int colbits, int diagbits, int offdiagbits, int n){
      if(row == n){
        results_.push_back(vector(n, string(n, '.')));  
        auto& result = results_.back();
        for(int row = 0; row < n; ++row){
          result[row][columns[row]] = 'Q';
        }
        return;
      }
      for(int col = 0; col < n; ++col){
        int flag = 1<>1, (offdiagbits|flag)<<1, n);
      }
      columns[row] = -1;
      return;
    }
    vector> results_;
};