题目描述

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

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

样例

Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

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

算法1

(位运算) $O(2^n)$

位运算的解法主要是使用数值的二进制位0/1来表示该位置能否放置皇后, 1表示可以放置, 0表示无法放置。
若放置是按照行的顺序一行一行地放置, 则在放置每一行的皇后时只需考虑列、主对角线、副对角线的情况。
列的情况比较简单, 若当前行的某一列放置了皇后, 则下一行的该列位置便无法放置皇后, 于是下一行的列的能否放置的情况由col | bit得出。而主、副对角线的位置则不一样一些，因为对角线是斜的，当前行的情况对下一行的影响会整体向右或向左偏移一格，以上述图中的样例为例，若在放置最顶上那一行时,d列放置了皇后，则下一行的c列和e列将都无法放置皇后，于是主副对角线的情况则分别由(m_dg | bit) >> 1 和(v_dg | bit) << 1得出。当某一行的所有位都无法放置或者总共已经放置了n个皇后,程序结束，否则继续递归。

C++ 代码

class Solution {
public:

    void countNQueens(int col, int m_dg, int v_dg, int u, int n, int& cnt){
        if(u == n){
            cnt ++;
            return;
        }
        // 将超过n位的数值置零
        int bits = ~(col | m_dg | v_dg) & (1 << n) - 1;

        while(bits){
            // 取最低位的1
            int bit = bits & (-bits);
            /* 将该位置放置皇后, 在处理下一行时, 该列无法放置皇后, 
            同时主对角线右移和副对角线左移的位置无法放置皇后*/
            countNQueens(col | bit, (m_dg | bit) >> 1, (v_dg | bit) << 1, u + 1, n, cnt);
            // 去除最低位的1
            bits &= bits - 1;
        }
    }

    int totalNQueens(int n) {
        if(n < 1){
            return n;
        }
        int cnt = 0;
        countNQueens(0, 0, 0, 0, n, cnt);
        return cnt;
    }
};